백준 3055: 탈출

문제 요약

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

이전 [C++] 백준 5427: 불 문제와 거의 동일한데, 다만 이번에는 고슴도치가 'D'까지 가는게 목표이며, 물은 'D'까지 침범할 수 없다는 조건이 추가되었다.

if문만 조금 더 손보면 풀 수 있다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

char ary[1000][1000] = { 0, };
queue<pair<short, short>> loc, water;

int main()
{
	int w, h, level = 0;
	short f, s;
	bool solve;
	solve = false;
	scanf("%d%d\n", &h, &w);
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			scanf("%c", &ary[i][j]);
			if (ary[i][j] == 'S') loc.push({ i,j });
			else if (ary[i][j] == '*') water.push({ i,j });
		}
		getchar();
	}
	while (!loc.empty()) {
		level++;
		int qsize = water.size();
		
		for (int i = 0; i < qsize; i++) {
			f = water.front().first;
			s = water.front().second;
			water.pop();
			if (f < h - 1 && ary[f + 1][s] != 'X' && ary[f + 1][s] != '*' && ary[f + 1][s] != 'D') {
				ary[f + 1][s] = '*';
				water.push({ f + 1, s });
			}
			if (f > 0 && ary[f - 1][s] != 'X' && ary[f - 1][s] != '*' && ary[f - 1][s] != 'D') {
				ary[f - 1][s] = '*';
				water.push({ f - 1, s });
			}
			if (s < w - 1 && ary[f][s + 1] != 'X' && ary[f][s + 1] != '*' && ary[f][s + 1] != 'D') {
				ary[f][s + 1] = '*';
				water.push({ f, s + 1 });
			}
			if (s > 0 && ary[f][s - 1] != 'X' && ary[f][s - 1] != '*' && ary[f][s - 1] != 'D') {
				ary[f][s - 1] = '*';
				water.push({ f, s - 1 });
			}
		}
		qsize = loc.size();
		for (int i = 0; i < qsize; i++) {
			f = loc.front().first;
			s = loc.front().second;
			loc.pop();
			if (f < h - 1 && (ary[f + 1][s] == '.' || ary[f + 1][s] == 'D')) {
				if (ary[f + 1][s] == 'D') {
					solve = true;
					break;
				}
				ary[f + 1][s] = 'S';
				loc.push({ f + 1, s });
			}
			if (f > 0 && (ary[f - 1][s] == '.' || ary[f - 1][s] == 'D')) {
				if (ary[f - 1][s] == 'D') {
					solve = true;
					break;
				}
				ary[f - 1][s] = 'S';
				loc.push({ f - 1, s });
			}
			if (s < w - 1 && (ary[f][s + 1] == '.' || ary[f][s + 1] == 'D')) {
				if (ary[f][s + 1] == 'D') {
					solve = true;
					break;
				}
				ary[f][s + 1] = 'S';
				loc.push({ f, s + 1 });
			}
			if (s > 0 && (ary[f][s - 1] == '.' || ary[f][s - 1] == 'D')) {
				if (ary[f][s - 1] == 'D') {
					solve = true;
					break;
				}
				ary[f][s - 1] = 'S';
				loc.push({ f, s - 1 });
			}
		}
		if (solve) break;
	}
	if (solve) printf("%d", level);
	else printf("KAKTUS");
	return 0;
}