굳건하게

안녕하세요.

여행벌입니다.

오늘은 BOJ 7569번 토마토 문제를 풀어보겠습니다.

전형적인 BFS를 이용한 문제인데요! 다만 3차원이라 방향을 다룰게 많다는 점이 특이한 것 같습니다.

https://www.acmicpc.net/problem/7569

[알고리즘풀이]

BFS 탐색을 이용해서, 순회를 진행하고 익지않은토마토가 있는지 없는지 체크한다.

#include<iostream>
#include<queue>

using namespace std;

int box[100][100][100];

// 위 오 아 왼 윗층 아랫층
int x_d[6] = { -1, 0, 1, 0, 0, 0 };
int y_d[6] = { 0, 1, 0, -1, 0, 0 };
int z_d[6] = { 0, 0, 0, 0, 1, -1 };

int BFS(int, int, int, int, int, int);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	queue<int> x, y, z, l;
	int r, c, h;
	cin >> c >> r >> h;

	for(int k = 0; k < h; k++)
		for (int i = 0; i < r; i++)
			for (int j = 0; j < c; j++){
				cin >> box[i][j][k];
				if (box[i][j][k] == 1) {
					x.push(i);
					y.push(j);
					z.push(k);
					l.push(0);
				}
			}

	int max = 0;
	while (!x.empty()) {
		int s_x = x.front(), s_y = y.front(), s_z = z.front(), s_l = l.front();
		x.pop(), y.pop(), z.pop(), l.pop();
		for (int i = 0; i < 6; i++) {
			int n_x = s_x + x_d[i];
			int n_y = s_y + y_d[i];
			int n_z = s_z + z_d[i];
			if (0 <= n_x && n_x < r && 0 <= n_y && n_y < c && 0 <= n_z && n_z < h && box[n_x][n_y][n_z] == 0) {
				box[n_x][n_y][n_z] = 1;
				x.push(n_x);
				y.push(n_y);
				z.push(n_z);
				l.push(s_l + 1);
				if (max < s_l + 1)
					max = s_l + 1;
			}
		}
	}
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			for (int k = 0; k < h; k++) 
				if (box[i][j][k] == 0) {
					cout << "-1";
					return 0;
				}
	cout << max;
	return 0;
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

방학이 끝나기 전에 예전에 풀었던 문제들도 포스팅을 해보려고 합니다.

https://www.acmicpc.net/problem/1004

[알고리즘설계]

출발점과 도착점이 원의 안과 밖으로 나뉜다면 카운트를 해준다.

#include<iostream>

using namespace std;

int main(void) {
	int total_case, planet_case; //테스트 케이스 횟수, 행성 갯수
	int x1, y1, x2, y2; //출발점좌표와 도착점좌표
	int count = 0; //행성이탈횟수를 세주는 변수
	int x3, y3, r; //행성의 중점과 반지름
    cin >> total_case;
	while (total_case > 0) { //전체 테스트 횟수
		count = 0; //테스트마다 count를 초기화 해준다.
        cin >> x1 >> y1 >> x2 >> y2 >> planet_case;
		for (int i = 0; i < planet_case; i++) {
        	cin >> x3 >> y3 >> r;
			if (((((x1 - x3)*(x1 - x3) + (y1 - y3)*(y1 - y3)) >= r * r)
				&& ((x2 - x3)*(x2 - x3) + (y2 - y3)*(y2 - y3) <= r * r))
				//출발점이 원 밖, 도착점이 원 안 인 경우
				||
				((((x1 - x3)*(x1 - x3) + (y1 - y3)*(y1 - y3)) <= r * r)
					&& ((x2 - x3)*(x2 - x3) + (y2 - y3)*(y2 - y3) >= r * r))) {
				count++;
			}
				//출발점이 원 안, 도착점이 원 밖 인 경우
		}
		total_case--;
        cout << count << '\n';
	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

문제는 단순하지만, 0.25초라는 짧은 제한 시간 때문에 DP를 이용해야만 풀 수 있는 문제입니다.

https://www.acmicpc.net/problem/1003

[알고리즘설계]

fibonachi(N)을 구하는데, fibonachi(1), fibonachi(0)이 몇 번 호출되는지 구하기 위해서는

fibonachi(N-1), fibonachi(N-2)를 구하는데 fibonachi(1), fibonachi(0) 이 몇 번 호출되는지 알고있으면 해결됩니다.

2차원 DP배열[2][N]을 다음과 같이 정의합니다.

DP[0][i] : fibonachi(i)를 구하는데 fibonachi(0) 의 호출 횟수.

DP[1][i] : fibonachi(i)를 구하는데 fibonachi(1) 의 호출 횟수.

그러면 아래와 같은 방정식이 성립합니다.

DP[0][i+1] = DP[0][i] + DP[0][i-1]

DP[1][i+1] = DP[1][i] + DP[1][i-1]

#include<iostream>

using namespace std;

int call_list[2][41]; // fibonachi(n)에 대해서 0이 호출되는 횟수를 0행, 1이 호출되는 횟수를 1행에 저장한다.


int main(void) {
	call_list[0][0] = 1;
	call_list[1][1] = 1;
	int total_case;
	cin >> total_case;
	while(total_case>0){
		int input;
		cin >> input;
		for (int i = 2; i <= 40; i++) {
			call_list[0][i] = call_list[0][i - 1] + call_list[0][i - 2];
			call_list[1][i] = call_list[1][i - 1] + call_list[1][i - 2];
		}
		cout << call_list[0][input] << " " << call_list[1][input];
		if(total_case != 1)
			cout << endl;
		total_case--;
	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

오늘은 BFS 문제인 BOJ 1697 문제를 다뤄보겠습니다.

https://www.acmicpc.net/problem/1697

[알고리즘설계]

가능한 모든 경우를 BFS 탐색을 하며, 각 경우에 대해서 현재까지 몇 번 움직였는지 Count를 세줍니다.

가장 먼저 도착지점(End)에 도달하면, Count를 출력하며 종료합니다.

-주의사항

1.모든 경우에 대해서 움직이기 전에 가능한 index인지 체크해줘야 됩니다.

2.이미 와본 지점에 대해서는 더 진행할 필요가 없습니다.(이미 그전에 진행했으니까 Count가 클 수밖에 없음.)

#include<iostream>
#include<queue>

using namespace std;

void BFS(int, int);
bool check[100001];

int main(void) {
	int start, end;
	cin >> start >> end;
	BFS(start, end);
	return 0;
}

void BFS(int start, int end) {
	queue<int> q;
	queue<int> count;
	q.push(start);
	count.push(0);
	while (!q.empty()) {
		int x = q.front();
		int c = count.front();
		q.pop();
		count.pop();

		if (x == end) {
			cout << c;
			return;
		}
		if (x + 1 <= 100000 && !check[x+1]){
            check[x+1] = true;
			q.push(x + 1);
			count.push(c + 1);
		}
		if (2 * x <= 100000 && !check[2 * x]) {
            check[2*x] = true;
			q.push(2 * x);
			count.push(c + 1);
		}
		if (0 <= x-1 && !check[x-1]){
            check[x-1] = true;
			q.push(x - 1);
			count.push(c + 1);
		}
	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.