[백준 3055] 탈출 c++

# 문제링크

www.acmicpc.net/problem/3055

3055번: 탈출

매 분마다 고슴도치도 네 방향으로 움직이고, 물도 네 방향으로 움직이니까, queue를 두개 만들어주고 각각 돌도록 구현했다. 유의할 점은 Flooding 함수에서 stime과 time 을 비교하여 같지 않으면, 큐에서 pop을 해주면 안된다. 습관적으로 front()를 확인하고 pop()을 해주었는데, 조건이 맞지 않으면 pop()을 해주지 말아야 한다.

 

또 하나 기억할 점은 테스트 케이스를 여러 개 돌릴 때 사용한 배열을 꼭 초기화해주어야 한다는 것이다. 백준에서는 메인에서 한 테케만 돌리지만, 다른 사이트에서 이 문제를 풀었을 때 테케가 여러 개였다. 근데 visited 배열 초기화를 안해주어서 답이 계속 틀렸었다. 그것도 모르고 로직을 계속 붙들고 있었는데 너무너무 아쉬운 경험이다. 다음부터는 무조건 초기화 해야지...

 

# 제출 코드 

 

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

int R, C;
char map[52][52];
int xd[] = { 1, -1, 0, 0 };
int yd[] = { 0,0,1, -1 };
queue <pair<int, int>> flood; // 홍수
queue <pair<int, int>> q; // 고슴도치들
int visited[52][52];

void Flooding() {
	int y = flood.front().first;
	int x = flood.front().second;
	int stime = visited[y][x];
	int time;

	while (!flood.empty()) {
		y = flood.front().first;
		x = flood.front().second;
		time = visited[y][x];

		if (stime != time) break; // 한 바퀴만 돌기

		flood.pop(); 

		for (int i = 0; i < 4; i++) {
			int ny = y + yd[i];
			int nx = x + xd[i];

			if (ny < 1 || ny > R) continue;
			if (nx < 1 || nx > C) continue;
			if (visited[ny][nx] != 0)continue;
			if (map[ny][nx] == 'X' || map[ny][nx] == 'D') continue;
			visited[ny][nx] = visited[y][x] + 1;
			flood.push({ ny,nx });
		}
	}
}
int BFS() {
	int stime = 0, time;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		time = visited[y][x];

		if (time != stime && !flood.empty()) { // 1분 지날때 마다 
			Flooding();
			stime = time;
		}

		for (int i = 0; i < 4; i++) {
			int ny = y + yd[i];
			int nx = x + xd[i];

			if (ny < 1 || ny > R) continue;
			if (nx < 1 || nx > C) continue;

			if (map[ny][nx] == 'D') return time;

			if (visited[ny][nx] != 0)continue;
			if (map[ny][nx] == 'X') continue;
			visited[ny][nx] = visited[y][x] + 1;
			q.push({ ny,nx });
		}
	}
	return -1;
}

void Input() {
	scanf("%d %d", &R, &C);
	for (int i = 1; i <= R; i++) {
		scanf("%s", &map[i][1]); // 1, 1 부터 입력받음
		for (int j = 1; j <= C; j++) {
			if (map[i][j] == '*') { flood.push({ i,j }); visited[i][j] = 1; }
			if (map[i][j] == 'S') { q.push({ i,j }); visited[i][j] = 1; }
		}
	}
}
int main() {
	Input();
	int ret = BFS();
	if (ret == -1) printf("KAKTUS\n");
	else printf("%d\n", ret);
}