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

문제: www.acmicpc.net/problem/4179

4179번: 불!

 

 

문제풀이

 

BFS를 이용한 최단거리 문제

 

거리 배열을 2개를 선언하고

배열 1은 불의 BFS 순서를 저장하고 배열 2는 지훈이의 BFS 순서를 저장하였다.

 

배열 2의 BFS 순서를 저장할 때 저장하기 전 배열 1의 값과 비교하여 배열 1의 값이 배열 2의 값보다 작거나 같으면

불이 붙어있거나 지훈이와 불이 동시에 도착할 수 있는 즉, 갈 수 없는 좌표이므로 continue 해준다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;


string board[1000];
int dist1[1000][1000];
int dist2[1000][1000];

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

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

	for(int i=0; i<r; i++){ //dist1, dist2 모두 -1로 초기화
		fill(dist1[i], dist1[i]+c, -1);
		fill(dist2[i], dist2[i]+c, -1);
	}

	queue<pair<int,int>> q1; //불
	queue<pair<int,int>> q2; //지훈
	for(int i=0; i<r; i++){
		cin>>board[i];
		for(int j=0; j<c; j++){
			if(board[i][j] == 'F'){ //불 시작점
				q1.push({i,j});
				dist1[i][j] = 0;
			}
			
			if(board[i][j] == 'J'){ //지훈이 시작점
				q2.push({i,j});
				dist2[i][j] = 0;
			}
		}
	}

	while(!q1.empty()){ //불이 번지는 것을 먼저 bfs
		pair<int,int> cur = q1.front();
		q1.pop();

		for(int dir=0; dir<4; dir++){
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];

			if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
			if(dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue;

			dist1[nx][ny] = dist1[cur.first][cur.second] + 1;
			q1.push({nx,ny});
		}
	}

	while(!q2.empty()){ //지훈이 bfs
		pair<int,int> cur = q2.front();
		q2.pop();

		for(int dir=0; dir<4; dir++){
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];

			if(nx < 0 || nx >= r || ny < 0 || ny >= c){ //범위를 벗어났다는 것은 탈출을 의미
				cout<<dist2[cur.first][cur.second]+1;
				return 0;
			}

			if(dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
			if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.first][cur.second]+1) continue; //불이 이미 붙어있거나 바로 붙을 예정인 좌표

			dist2[nx][ny] = dist2[cur.first][cur.second] + 1;
			q2.push({nx,ny});
		}
	}
	
	cout<<"IMPOSSIBLE"; //두번째 while문에서 탈출을 하지못했다면 탈출이 불가능한 것이다.

	return 0;
}

 

 

결과