[ BOJ 오답노트 ] 4179 C++ : 불!

예제 1에서는 올바른 결과가 나왔지만

계속 "틀렸습니다"라고 떠서..

다른 테스트케이스를 확인해봤는데 역시나 올바르지 않았다.

 

 

(1) 불이 하나가 아닌 경우

[Input]
4 4
#F##
#F##
..J#
####

[Output]
IMPOSSIBLE

[Result]
3

반례 by. dontsaymyid

 

 

 

(2) 불이 갇혀있는 경우

5 5
#####
#F#J#
###.#
###.#
###.#

output : IMPOSSIBLE
answer : 4

반례 by. possible

 

 

(3) 내 코드 (수정 전)

# include<bits/stdc++.h>
using namespace std;
# define X first
# define Y second
string board[1000][1000];
int fire[1000][1000];
int jihun[1000][1000];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int r, c;
	cin >> r >> c;

	queue <pair<int, int>> Q_F;
	queue <pair<int, int>> Q_J;

	// 미로 입력받기
	string str;
	for (int i = 0; i < r; i++) {
		cin >> str;
		for (int j = 0; j < c; j++) {
			board[i][j] = str[j];

			if (str[j] == 'J') Q_J.push({ i, j });
			if (str[j] == 'F') Q_F.push({ i, j });
			if (str[j] == '#') {
				fire[i][j] = -1;
				jihun[i][j] = -1;
			}
		}
	}

	// 불 먼저 거리 저장하기 - 불이 여러 개인 상황을 고려해야 한다.
	while (!Q_F.empty()) {
		pair<int, int> cur = Q_F.front(); Q_F.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
			if (fire[nx][ny] > 0 || fire[nx][ny] == -1 || board[nx][ny] =="F") continue;
			fire[nx][ny] = fire[cur.X][cur.Y] + 1;
			Q_F.push({ nx, ny });
		}
	}

	// 지훈이 이동하기
	while (!Q_J.empty()) {
		pair<int, int> cur = Q_J.front(); Q_J.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 0 || ny < 0 || nx >= r || ny >= c) {
				cout << jihun[cur.X][cur.Y] + 1;
				return 0;
			}
			if (jihun[nx][ny] > 0 || jihun[nx][ny] == -1 || board[nx][ny] == "J") continue;
			if (jihun[cur.X][cur.Y] + 1 >= fire[nx][ny]) continue;
			if (jihun[cur.X][cur.Y] + 1 >= fire[nx][ny])
			jihun[nx][ny] = jihun[cur.X][cur.Y] + 1;
			Q_J.push({ nx, ny });
			
		}
	}
	cout << "IMPOSSIBLE";

	
}

 

 

(4) 내 코드 (수정 후)

# include<bits/stdc++.h>
using namespace std;
# define X first
# define Y second
string board[1000][1000];
int fire[1000][1000];
int jihun[1000][1000];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int r, c;
	cin >> r >> c;

	queue <pair<int, int>> Q_F;
	queue <pair<int, int>> Q_J;

	// 미로 입력받기
	string str;
	for (int i = 0; i < r; i++) {
		cin >> str;

		fill(fire[i], fire[i] + c, -1);
		fill(jihun[i], jihun[i] + c, -1);

		for (int j = 0; j < c; j++) {
			board[i][j] = str[j];

			if (str[j] == 'J') {
				Q_J.push({ i, j });
				jihun[i][j] = 0;
			}
			if (str[j] == 'F') {
				Q_F.push({ i, j });
				fire[i][j] = 0;
			}
		}
	}

	// 불 먼저 거리 저장하기 - 불이 여러 개인 상황을 고려해야 한다.
	while (!Q_F.empty()) {
		pair<int, int> cur = Q_F.front(); Q_F.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
			if (fire[nx][ny] >= 0 || board[nx][ny] =="#") continue;
			fire[nx][ny] = fire[cur.X][cur.Y] + 1;
			Q_F.push({ nx, ny });
		}
	}

	// 지훈이 이동하기
	while (!Q_J.empty()) {
		pair<int, int> cur = Q_J.front(); Q_J.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 0 || ny < 0 || nx >= r || ny >= c) {
				cout << jihun[cur.X][cur.Y] + 1;
				return 0;
			}
			if (jihun[nx][ny] >= 0 || board[nx][ny] == "#") continue;
			if (jihun[cur.X][cur.Y] + 1 >= fire[nx][ny] && fire[nx][ny] != -1) continue;
			
			jihun[nx][ny] = jihun[cur.X][cur.Y] + 1;
			Q_J.push({ nx, ny });
			
		}
	}
	cout << "IMPOSSIBLE";

	
}

 

수정된 코드에서 핵심은!

if (jihun[cur.X][cur.Y] + 1 >= fire[nx][ny] && fire[nx][ny] != -1) continue;

 

요것이다.

불이 확장하지 못했을 때에도 지훈이는 이동할 수 있다.

따라서 fire의 값이 -1일 때에도 지훈이는 이동할 수 있으니, 그 반대로 두 조건을 모두 만족하면 continue 하도록 만들었다.