[BFS]-연습-불!

< BFS > - < 골드 4 >

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

4179번: 불!

---

[ 4179 ] 불!

 

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

 

:: 입력 ::

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

:: 출력 ::

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

---

 

첫 제출에서는 조건문 안에 visit != 0  이렇게 써서 틀렸다고 생각하고 그걸 고쳐서 다시 냈음 솔직히 당연히 맞을 줄 알았는데 또 틀렸다고 해서 문제를 읽어보니까 최소 시간을 출력하라고 나와있는데 내가 짠 코드는 그냥 조건에 맞는 좌표가 나오면 그 시간을 바로 출력하게 해둠 그래서 최솟값을 계산하는 코드를 넣어서 수정했는데 또 틀림 그러고 정답코드를 봤음 정답코드를 보고 알아낸 건 BFS에서는 어차피 큐에 거리순으로 원소가 들어가게 되기때문에 따로 최소 시간을 구해줄 필요 없이  제일 먼저 조건을 만족하는게 최소 값이라는 거랑 내가 조건문을 더럽게 못 쓴다는거임 나는 거리를 저장하는 배열을 모두 0으로 세팅하고 입력 받는 도중에 J(지훈이의 위치)나 F(불의 시작점)이 나오면 그 곳을 1로 바꾸고 해당 지점에서 BFS를 돌렸는데 이 부분 조건문이 정답코드랑 달라서 내가 모르는 예외가 발생하는 것 같음 + 나는 지훈이의 시작점이나 불의 시작점은 BFS에서 빼도 된다고 생각해서 그 부분을 continue로 넘어가게 해두었는데 지금 생각해보니까 그러면 안되네 ,, 까지 쓰고 테스트 해봤는데 조건을 바꿔도 맞음 거리를 저장하는 배열에 대한 조건처리를 못한듯 조건문을 쓸 때 감으로 하지말고 확실히 머릿속에 정리해두고 짜기 !

 

  코드  

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int board[1001][1001];
int visit[1001][1001];
int fire_visit[1001][1001];

int main() {
	int dir_x[] = { 0, 1, 0, -1 };
	int dir_y[] = { 1, 0, -1, 0 };

	int r, c;
	cin >> r >> c;

	string line;
	queue<pair<int, int>> q;
	queue<pair<int, int>> fire_q;

	// 입력 받기
	for (int i = 0; i < r; i++) {
		cin >> line;
		for (int j = 0; j < c; j++) {
			if (line[j] == '#') board[i][j] = -1;
			else if (line[j] == 'J') { board[i][j] = 1; q.push({ i, j }); visit[i][j]++; }
			else if (line[j] == 'F') { board[i][j] = -1; fire_q.push({ i, j }); fire_visit[i][j]++; }
		}
	}

	//for (int i = 0; i < r; i++) {
	//	for (int j = 0; j < c; j++) {
	//		cout << board[i][j];
	//	}
	//	cout << "\n";
	//}

	// 불 BFS 돌면서 fire_visit 배열에 각 칸까지 걸리는 시간 저장
	while (!fire_q.empty()) {
		int x = fire_q.front().first;
		int y = fire_q.front().second;
		fire_q.pop();

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

			if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
			if (fire_visit[nx][ny] != 0 || board[nx][ny] != 0) continue;

			fire_visit[nx][ny] = fire_visit[x][y] + 1;
			fire_q.push({ nx,ny });
		}
	}

	/*for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << fire_visit[i][j];
		}
		cout << "\n";
	}*/

	// fire_visit에 저장된 불이 도달하는 시간과 지훈이의 걸음을 비교해서 시간 출력
	// int time = r*c; << 최소 시간을 계산하기 위한 변수
	// bool escape = false; << 탈출 가능여부를 저장
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

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

			if (nx < 0 || nx >= r || ny < 0 || ny >= c) 
				// continue;
			{
				// nx와 ny가 해당 값에 도달했다는 것은 탈출에 성공했음을 의미 !
				// x,y가 가장자리 일떄 nx,ny 값이 이 범위에 들어오니까
				cout << visit[x][y];
				return 0;
			}
			if (visit[nx][ny] != 0 || board[nx][ny] != 0) continue;

			// visit[nx][ny] = visit[x][y] + 1;
			if (visit[nx][ny] < fire_visit[nx][ny]) {
				visit[nx][ny] = visit[x][y] + 1;
				q.push({ nx,ny });
				// if (nx == 0 || ny == 0 || nx == (r - 1) || ny == (c - 1)) {
					// 이렇게 하면 최단시간이라는 조건을 만족하지 못함 ! 
					// cout << visit[nx][ny];
					// return 0;
					// 어차피 큐에는 거리순으로 들어가기 떄문에 처음 고안했던대로 제일 먼저 조건을 만족하는 경우의 결과를 출력하는 게 맞음
					// 정답코드와는 조건문을 사용하는 방식이 달랐음
					// if (time > visit[nx][ny]) { time = visit[nx][ny]; escape = true; }
				//}
				/*else {
					q.push({ nx,ny });
				}*/
			}
		}

	}

	//for (int i = 0; i < r; i++) {
	//	for (int j = 0; j < c; j++) {
	//		cout << visit[i][j];
	//	}
	//	cout << "\n";
	//}

	//if (escape) cout << time;
	//else cout << "IMPOSSIBLE";
	cout << "IMPOSSIBLE";
}

  최종 정답  코드  

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int board[1001][1001];
int visit[1001][1001];
int fire_visit[1001][1001];

int main() {
	int dir_x[] = { 0, 1, 0, -1 };
	int dir_y[] = { 1, 0, -1, 0 };

	int r, c;
	cin >> r >> c;

	string line;
	
	queue<pair<int, int>> q;
	queue<pair<int, int>> fire_q;

	// 거리를 저장할 배열을 -1로 초기화 해줌
	for (int i = 0; i < r; i++) {
		fill(fire_visit[i], fire_visit[i] + c, -1);
		fill(visit[i], visit[i] + c, -1);
	}

	// 입력 받기
	for (int i = 0; i < r; i++) {
		cin >> line;
		for (int j = 0; j < c; j++) {
			if (line[j] == '#') board[i][j] = -1;
			else if (line[j] == 'J') {
            // board[i][j] =1;
				q.push({ i, j });
				visit[i][j] = 0;
			}
			else if (line[j] == 'F') {
            // board[i][j] =1;
				fire_q.push({ i, j });
				fire_visit[i][j] = 0;
			}
		}
	}

	// 불 BFS 돌면서 fire_visit 배열에 각 칸까지 걸리는 시간 저장
	while (!fire_q.empty()) {
		int x = fire_q.front().first;
		int y = fire_q.front().second;
		fire_q.pop();

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

			
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            // board[nx][ny]가 -1 일 때랑 ( J와 F를 1로 처리한 후 ) 0이 아닐 때 모두 정답 
			if (fire_visit[nx][ny] >= 0 || board[nx][ny] == -1 /* board[nx][ny] != 0 */) continue;

			fire_visit[nx][ny] = fire_visit[x][y] + 1;
			fire_q.push({ nx,ny });
		}
	}

	// fire_visit에 저장된 불이 도달하는 시간과 지훈이의 걸음을 비교해서 시간 출력
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

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

			if (nx < 0 || nx >= r || ny < 0 || ny >= c)
			{
				// nx와 ny가 해당 값에 도달했다는 것은 탈출에 성공했음을 의미 !
				// x,y가 가장자리 일떄 nx,ny 값이 이 범위에 들어오니까
				cout << visit[x][y]+1;
				return 0;
			}
            // board[nx][ny]가 -1 일 때랑 ( J와 F를 1로 처리한 후 ) 0이 아닐 때 모두 정답 
			if (visit[nx][ny] >= 0 || board[nx][ny] == -1 /* board[nx][ny] != 0 */) continue;
			if (fire_visit[nx][ny] != -1 && fire_visit[nx][ny] <= visit[x][y]+1) continue;
				
			visit[nx][ny] = visit[x][y] + 1;
			q.push({ nx,ny });
		}
	}

	cout << "IMPOSSIBLE";
}