4179 - 불!

문제

문제가 길어 링크로 대체했습니다.
4179번: 불!

코드

#include <bits/stdc++.h>
using namespace std;
#define INF 2100000000

int n,m,y,x,ret;
int f[1004][1004];
int p[1004][1004];
char a[1004][1004];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0,1,0,-1};

int main(){
	queue<pair<int,int>>q;
	int jy, jx;
	fill(&f[0][0], &f[0][0] + 1004*1004, INF);
	cin >> n >> m;
	
	for(int i = 0; i <n; i++){
		for(int j = 0; j <m; j++){
			cin >> a[i][j];
			if(a[i][j] == 'F') f[i][j] = 1, q.push({i,j});
			else if(a[i][j] == 'J'){
				 jy = i;
				  jx = j;
			}
		}
	}
	
	while(q.size()){
		tie(y,x) = q.front();
		q.pop();
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			if(f[ny][nx] != INF || a[ny][nx] == '#') continue;
			f[ny][nx] = f[y][x] + 1;
			q.push({ny,nx});
		}
	}
	
	p[jy][jx] = 1;
	q.push({jy,jx});
	while(q.size()){
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		
		if(x == m-1 || y == n-1 || y == 0 || x == 0){
			ret = p[y][x];
			break;
		}
		
		for(int i = 0; i <4; i++){
			int ny = y+ dy[i];
			int nx = x+ dx[i];
			if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			if(p[ny][nx] || a[ny][nx] == '#') continue;
			if(f[ny][nx] <= (p[y][x] + 1)) continue;
			p[ny][nx] = p[y][x] + 1;
			q.push({ny,nx});
		}
	}
	if(ret != 0) cout << ret << '\n';
	else cout << "IMPOSSIBLE" << '\n';
}

풀이

가중치가 없는 최단거리를 구한다 --> 웬만하면 BFS다.
BFS로 불을 먼저 보내고 불이 이동한 시간보다 낮으면 사람이 갈 수 있는 구조다.
재귀로 하기에 머리가 아파서 main 함수 내에 불을 먼저 BFS한다.
불이 퍼져있는 정보를 기반으로 사람도 BFS를 한다.
사람은 기저사례에 탈출 조건을 적어주고 ret 값이 있으면 출력 없으면 IMPOSSIbLE 출력이다.
앞쪽에 f배열에 값을 넣어준건 불이 없을 때를 대비한 수식이다.
다 맞았는데 몇 번 틀리다고 해서 하나씩 생각해보니 할당해놓은 f(불) 배열을 할당하지 않아서 생기는 오류였다.
초기 값을 할당했기 때문에 불이 있는 좌표 i, j에서 f[i][j]를 할당하지 않으면 INF+1이 되어 무조건 사람이 지나갈 수 있게 되버린다.

결과

후기

매번 푸는 탐색 문젠데 어쩜 이렇게 색다르게 하나씩 안맞는지 모르겠다.
감은 알겠는데 모든 문제가 약간의 구현 차이가 있어서 힘들다.
그리고 골드로 넘어오니 디테일적인 요소를 좀 더 신경써야 할 듯 하다.
변수 할당을 너무 신경 안쓰고 풀어 왔다는 느낌이 들었다.