[백준 4179번 / C++] 불!

bfs 를 이용해서 풀면 되는 문제이다. 

 

#접근방법

 

이 문제는 생각보다 예외사항이 많았다. 이 점들을 고려하지 못한채로 접근해서 수정작업이 좀 필요했다. 

그래서 문제를 풀기 전에 지문을 꼼꼼히 읽고 접근해야할 습관이 필요하다고 뼈저리 느꼈던 문제이다. 

 

이 문제를 요약하자면 불이 상하좌우로 먼저 퍼지고 나서 지훈이가 불을 피해서 지도의 끝에 도착하면 빠져나갈 수 있다. 그냥 전형적인 BFS() 문제인데 예외사항이 무엇인지 한번 살펴보자. 

 

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

 

문제를 보면 위의 문장 한줄이 나와있다. 여기서 유추를 했어야만 했다. 

즉, "J는 입력에서 하나만 주어질 수 있다" 라는 말은 F는 입력에서 하나일 수도 있고 없을 수도 있고 두개 이상일 수도 있다는 뜻이다. 

 

나는 처음 접근할 때 아무생각없이 문제 예제 처럼 불을 하나라고만 생각하고 코드를 짰는데 계속해서 이상한 값이 떠서 다시 문제를 읽어봤다. 그렇기 때문에 다른 사람들도 불이 하나가 아닐거라는 가정을 머릿속에 담아두고 접근하자. 

 

즉, 입력받은 불의 모든 위치를 큐에 담아서 각지에 위치한 불을 동시에 퍼지게 만들고 나서 지훈이를 이동시키면 된다. 

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <tuple>
#include <string>
using namespace std;
vector <string> map; 
vector <string> visited; 
queue <pair<int, int>> j_l; //지훈위치
queue <pair<int, int>> f_l; //불위치
int m, n; 
int dx[4] = { 0,0,1,-1 }; 
int dy[4] = { 1,-1,0,0 }; 

void bfs() {
	int result = 0; 
	while (!j_l.empty()) {
		//f_l 불, j_l 지훈 
		int n1 = f_l.size(); 
		while (n1--) {
			int fx, fy; 
			tie(fy, fx) = f_l.front();
			f_l.pop();
			for (int i = 0; i < 4; i++) {
				int nx = fx + dx[i];
				int ny = fy + dy[i];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
				if (map[ny][nx] == '#' || map[ny][nx] == 'F')continue;
				map[ny][nx] = 'F';
				f_l.push({ ny,nx });
			}
		}
		n1 = j_l.size();
		while (n1--) {
			int  jx, jy;
			tie(jy, jx) = j_l.front();
			j_l.pop();
			for (int i = 0; i < 4; i++) {
				int nx = jx + dx[i];
				int ny = jy + dy[i];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
					cout << result + 1;
					return;
				}
				if (map[ny][nx] == '#' || visited[ny][nx] == '1' || map[ny][nx] == 'F')continue;
				visited[ny][nx] = '1';
				j_l.push({ ny,nx });
			}
		}
		result++; 
	}
	cout << "IMPOSSIBLE"; 
	return; 

}

int main() {
	cin >> m >> n; 
	map.resize(m, ""); 
	visited.resize(m, "");
	for (int i = 0; i < m; i++) {
		cin >> map[i]; 
		for (int j = 0; j < n; j++) {
			visited[i] += '0'; 
			if (map[i][j] == 'J') {
				j_l.push({ i, j });
				visited[i][j] = '1'; 
			}
			else if (map[i][j] == 'F') {
				f_l.push({ i, j });
				visited[i][j] = '1'; 
			}
		}
	}
	bfs(); 
}

 

4179번: 불!