[백준][bfs] 4179 불! c++ 구현

목차

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

문제

 

문제 구현 방향

bfs로 전처리를 해주고 다시 bfs를 통해 최단 거리를 구해주는 문제이다.. 

변수명을 잘 못지어서 많이 헤맸다 ㅠㅠ 변수명은 식별이 잘되게 적도록 하자

 

 

문제 풀이 시 주의점

불이 하나가 아닐 수도 있다는 사실을 명심해야 한다. 지훈이는 한명 고정이다

 

문제 예 설명

지훈이 퍼지는 시간 bfs갱신

#	#	#	#
#	1	2	#
#	2	3	#
#	3	4	#

 

불 퍼지는 시간 bfs 갱신

#	#	#	#
#	2	1	#
#	3	2	#
#	4	3	#

 

지훈이와 불이 퍼진 경로값을 이용해  (지훈이 경로 시간 < 불 경로 시간)일 경우 경로 갈 수 있음

 

#	#	#	#
#	1	0	#
#	2	0	#
#	3	0	#

 

따라서 최단 경로는 3

 

코드 구현

#include <iostream>
#include <vector>
#include<queue>
#include<algorithm>

using namespace std;

char board[1000][1000] = { 0 };
int visitJ[1000][1000] = { 0 };  //지훈이의 탐색 전처리
int visitF[1000][1000] = { 0 };  //불이 퍼지는 경우 하나하나
int minvisitF[1000][1000] = { 0 };  //불이 퍼진 것들 중에 최단경로만 갱신

int visit[1000][1000] = { 0 };  //지훈이의 탐색 
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int R, C;
vector<pair<int, int>> Fs;

void mins() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if ((minvisitF[i][j] > visitF[i][j]))
				minvisitF[i][j] = visitF[i][j];
		}
	}
}

void bfsJ(int Jx, int Jy) {
	queue<pair<int, int>> qJ;
	visitJ[Jy][Jx] = 1;
	qJ.push({ Jx, Jy });
	while (!qJ.empty()) {
		int x = qJ.front().first;
		int y = qJ.front().second;
		qJ.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || nx > C - 1 || ny < 0 || ny > R - 1)
				continue;
			if (board[ny][nx] == '#' || visitJ[ny][nx])
				continue;
			visitJ[ny][nx] = visitJ[y][x] + 1;
			qJ.push({ nx, ny });
		}
	}
}

void bfsF(int Fx, int Fy) {
	queue<pair<int, int>> qF;
	visitF[Fy][Fx] = 1;
	qF.push({ Fx, Fy });
	while (!qF.empty()) {
		int x = qF.front().first;
		int y = qF.front().second;
		qF.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx > C - 1 || ny < 0 || ny > R - 1)
				continue;
			if (board[ny][nx] == '#' || visitF[ny][nx])
				continue;
			visitF[ny][nx] = visitF[y][x] + 1;
			qF.push({ nx, ny });
		}
	}
	mins();
}

void bfs(int Jx, int Jy) {
	queue<pair<int, int>> q;
	visit[Jy][Jx] = 1;
	q.push({ Jx, Jy });
	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 + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx > C - 1 || ny < 0 || ny > R - 1)  
				continue;
			if (board[ny][nx] == '#' || visit[ny][nx])
				continue;
			if (visitJ[ny][nx] >= minvisitF[ny][nx]) //핵심 포인트
				continue;

			visit[ny][nx] = visit[y][x] + 1;
			q.push({ nx, ny });
		}
	}
}
void clear() {  //배열 초기화
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			visitF[i][j] = 0;
		}
	}
}

int main() {

	int Jx, Jy;
	int Fx, Fy;
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> board[i][j];
			minvisitF[i][j] = 1000000;
			if (board[i][j] == 'J') {
				Jx = j;
				Jy = i;
			}
			else if (board[i][j] == 'F') {
				Fs.push_back({ j, i });
			}
		}
	}
	bfsJ(Jx, Jy);
	for (auto k : Fs) {
		clear();
		bfsF(k.first, k.second);
	}
	bfs(Jx, Jy);

	int min = 100000;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (i == 0 || i == R - 1 || j == 0 || j == C - 1) {
				if (visit[i][j] != 0) {
					if (min > visit[i][j])
						min = visit[i][j];
				}

			}
		}
	}
	if (min == 100000)
		cout << "IMPOSSIBLE";
	else
		cout << min;
}