BOJ 5465 : 곰돌이

알고리즘 문제 전체 링크

 

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

 

이후 설명 및 입/출력은 링크 참고

 

queue에는 좌표 (r, c)와 depth(곰이 움직인 거리)를 담을 수 있도록 구조체를 아래와 같이 선언한다.

typedef struct st
{
	int r;
	int c;
	int depth;
}QUEUE;

QUEUE queue[MAX * MAX];
int wp, rp;

 

주어지는 input의 알파벳은 숫자로 변경한다. 

그리고 곰돌이의 최초 위치와 도착해야하는 집의 좌표는 따로 (sr, sc), (er, ec)에 저장한다.

void input()
{
	int change['Z' + 1] = { 0 };

	change['T'] = -1; /* 나무 */
	change['G'] = 0;  /* 빈 칸 */
	change['H'] = 1;  /* 벌집 */
	change['M'] = 0;  /* 빈 칸 + 곰돌이 최초 위치 */
	change['D'] = 0x7fff0000; /* 곰돌이의 집 */

	scanf("%d %d", &N, &S);

	for (int r = 1; r <= N; r++)
	{
		scanf("%s", str + 1);
		for (int c = 1; c <= N; c++)
		{
			if (str[c] == 'M')
			{
				sr = r;
				sc = c;
			}
			else if (str[c] == 'D')
			{
				er = r;
				ec = c;
			}

			MAP[r][c] = change[str[c]];
		}
	}
}

---

main에서 input을 실행한 후, 벌들을 queue에 담는다.

int main(void)
{
	int right, left, mid, ans;

	input();

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 1) /* 벌들을 모두 queue에 담는다. */
			{
				queue[wp].r = r;
				queue[wp++].c = c;
			}
		}
	}
    
	BFS1(); /* 벌들을 이용해 벌이 모두 채워질 때 까지 BFS 실행 */
    
    ...
}

 

그리고 BFS1()을 실행하여, 벌들을 퍼뜨려보자.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void BFS1()
{
	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

			if (MAP[nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;
				MAP[nr][nc] = MAP[out.r][out.c] + 1;
			}
		}
	}
}

 

위의 코드를 실행하면 예제 입력 1과 예제 입력 2의 경우는 아래와 같다.

 

M - 출발 위치 / D - 도착 위치

나무(-1)는 편의상 x로 나타내었고, 1은 벌집의 위치다.

예제 입력 1 vs 예제 입력 2

 

BFS1()이 종료되면 MAP에 X 초 후의 벌들의 위치는 X + 1 임을 알 수 있다.

(최초 시작이 1이므로 X + 1 초)

 

---

시간에 대한 벌들의 위치를 알게 되었다.

위 예제 모두 곰돌이는 1분에 S = 3 칸씩 움직여서 D로 도달할 수 있다.

 

왼쪽의 예제는 1분 동안 꿀을 먹을 수 있고, 오른쪽은 2분 동안 꿀을 먹을 수 있다.

실제로 가능한지 확인해보자.

 

각각 T = 1, T = 2초 후의 벌들의 위치가 된다.

 

곰돌이(M)는 S = 3칸 씩 움직일 수 있다.

현재 벌들의 위치를 고려하여 곰이 움직일 수 있는 범위는 빨간색으로 표시하였다.

 

다시 1초가 지난 후 벌들의 위치는 아래와 같다.

 

이때, 곰이 움직일 수 있는 위치는 아래와 같다.

T = 2초일 때, 곰이 집 D에 도착할 수 있다.

 

다시 1초가 지나면 오른쪽의 벌들이 움직인다.

 

그리고 곰이 D에 도착한다.

 

왼쪽 곰은 1초 동안 꿀을 먹어 D에 도착하였고, 오른쪽 곰은 2초 동안 꿀을 먹은 후 D에 도착하였다.

따라서 예제 입력 1, 2의 답은 각각 1, 2가 된다.

---

곰돌이가 꿀을 먹을 수 있는 가장 긴 시간을 X라고 하자.

그러면 X + 1 초 동안 꿀을 먹으면 벌들 때문에 집에 도착할 수 없다.

그리고 X - 1 초 동안 꿀을 먹으면 집에 도착할 수 있다.

(당연히, 꿀을 안먹고 빨리 출발해야 집에 도착할 가능성이 크다.)

 

따라서 이분 탐색을 이용해 M초 뒤에 출발하면 집에 도착할 수 있는지 확인하면 된다.

집에 도착할 수 있다면, M을 증가한다.

집에 도착할 수 없다면, M을 감소하면 된다.

 

가장 짧은 시간 left = 0, 가장 긴 시간 right = N * N 으로 잡고 이분 탐색을 이용하여 답을 구한다.

(벌들이 퍼지는 시간은 장애물을 고려해도 길어봤자 N²보다 작지만 넉넉히 잡는다.)

BFS2에 시간을 넘겨주면, 그 시간 동안 꿀을 먹은 후, 출발하여 집에 도착할 수 있는지 알려준다.

int main(void)
{
	int right, left, mid, ans;

	input();

	...

	BFS1(); /* 벌들을 이용해 벌이 모두 채워질 때 까지 BFS 실행 */

	left = 0;
	right = N * N;
	ans = -1;
	while (left <= right)
	{
		mid = (left + right) / 2;

		if (BFS2(mid)) ans = mid, left = mid + 1;
		else right = mid - 1;
	}

	printf("%d\n", ans);

	return 0;
}

---

MAP에 X 초 후의 벌들의 위치가 적혀 있으므로,

queue의 depth(=mid)를 넣어서 해당 위치에 갈 수 있는지 판단할 수 있다.

int BFS2(int mid)
{
	if (mid >= MAP[sr][sc] - 1) return 0;

	wp = rp = 0;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			visit[r][c] = 0;

	queue[wp].r = sr;
	queue[wp].c = sc;
	queue[wp++].depth = mid;

	visit[sr][sc] = 1;

	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		if (out.r == er && out.c == ec) return 1; /* 도착할 수 있는 경우 */

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
			if (MAP[nr][nc] == -1 || visit[nr][nc] != 0) continue;
			if ((mid + (out.depth - mid + 1) / S) >= (MAP[nr][nc] - 1)) continue;

			queue[wp].r = nr;
			queue[wp].c = nc;
			queue[wp++].depth = out.depth + 1;

			visit[nr][nc] = 1;
		}
	}

	return 0; /* 도착 실패 */
}

 

경계를 벗어나거나 벽이거나 방문한 곳은 queue에 담지 않는다.

그리고 아래의 경우에도 queue에 담지 않는다. 그렇게 해서 집의 좌표 (er, ec)에 도착하면 1을 return 한다.

if ((mid + (out.depth - mid + 1) / S) >= (MAP[nr][nc] - 1)) continue;

 

out.depth는 곰이 움직이는 거리의 기록이다.

하지만 곰은 1초 동안 S칸을 움직일 수 있기 때문에 갈 수 있는 위치를 

(현재 위치 - 시작 시간 + 1)에서 S칸을 나누는 과정을 통해 구할 수 있다.

(1초 부터 시작하였으므로 1을 더한다.)

 

예제 입력 2의 T = 3초인 경우를 보자.

오른쪽은 실제 곰의 발자국을 파란색으로 표시하였다.

(3, 3) 위치의 곰이 갈 수 있는 범위는 위의 공식으로 구할 수 있다.

 

 

mid = 2인 경우고 (3, 3)의 depth는 5이므로, 2 + (5 - 2 + 1) / 3 = 2 + 4 / 3 = 3이 된다.

3 >= MAP[nr][nc] - 1인 경우는 queue에 담지 않으므로,

4 >= MAP[nr][nc] → MAP이 5이상인 경우만 queue에 담을 수 있다.

 

BFS2가 1칸씩 탐색을 하므로,

곰이 움직인 거리 depth, 움직일 수 있는 칸 S, 시간에 대한 벌들의 위치 MAP에 대한 조건이 복잡해진다.

(큐에 담을 수 있는 조건이 까다로워진다.)

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (1010)

int N, S;
int MAP[MAX][MAX];
int visit[MAX][MAX];
char str[MAX];

int sr, sc, er, ec;

typedef struct st
{
	int r;
	int c;
	int depth;
}QUEUE;

QUEUE queue[MAX * MAX];
int wp, rp;

void input()
{
	int change['Z' + 1] = { 0 };

	change['T'] = -1; /* 나무 */
	change['G'] = 0;  /* 빈 칸 */
	change['H'] = 1;  /* 벌집 */
	change['M'] = 0;  /* 빈 칸 + 곰돌이 최초 위치 */
	change['D'] = 0x7fff0000; /* 곰돌이의 집 */

	scanf("%d %d", &N, &S);

	for (int r = 1; r <= N; r++)
	{
		scanf("%s", str + 1);
		for (int c = 1; c <= N; c++)
		{
			if (str[c] == 'M')
			{
				sr = r;
				sc = c;
			}
			else if (str[c] == 'D')
			{
				er = r;
				ec = c;
			}

			MAP[r][c] = change[str[c]];
		}
	}
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void BFS1()
{
	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

			if (MAP[nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;
				MAP[nr][nc] = MAP[out.r][out.c] + 1;
			}
		}
	}
}

int BFS2(int mid)
{
	if (mid >= MAP[sr][sc] - 1) return 0;

	wp = rp = 0;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			visit[r][c] = 0;

	queue[wp].r = sr;
	queue[wp].c = sc;
	queue[wp++].depth = mid;

	visit[sr][sc] = 1;

	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		if (out.r == er && out.c == ec) return 1; /* 도착할 수 있는 경우 */

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
			if (MAP[nr][nc] == -1 || visit[nr][nc] != 0) continue;
			if ((mid + (out.depth - mid + 1) / S) >= (MAP[nr][nc] - 1)) continue;

			queue[wp].r = nr;
			queue[wp].c = nc;
			queue[wp++].depth = out.depth + 1;

			visit[nr][nc] = 1;
		}
	}

	return 0; /* 도착 실패 */
}

int main(void)
{
	int right, left, mid, ans;

	input();

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 1) /* 벌들을 모두 queue에 담는다. */
			{
				queue[wp].r = r;
				queue[wp++].c = c;
			}
		}
	}

	BFS1(); /* 벌들을 이용해 벌이 모두 채워질 때 까지 BFS 실행 */

	left = 0;
	right = N * N;
	ans = -1;
	while (left <= right)
	{
		mid = (left + right) / 2;

		if (BFS2(mid)) ans = mid, left = mid + 1;
		else right = mid - 1;
	}

	printf("%d\n", ans);

	return 0;
}