BaekJoon 4179번: 불!

풀이법

BFS를 이용한다면 정답의 실마리를 찾을 수 있는 문제이나, 낮은 정답률이 말해주듯 난이도가 꽤 있는 편이다.

두 번의 bfs를 이용하여, 불이 이동하는 경로를 먼저 구한 후, 지훈이가 이동할 수 있는 경로를 비교하는 방법으로 문제를 해결했다. 해당 문제의 핵심 logic과 검색을 통해 쉽게 구할 수 있는 Hidden TC는 source code 밑에 기술하였다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
bool visited[1001][1001];
bool visitedF[1001][1001];
char arr[1001][1001];
int ansj[1001][1001];
int ansf[1001][1001];
int vx[4] = { 1,0,-1,0 };
int vy[4] = {0,-1,0,1};
queue<pair<int, int>> fire;
int r, c;
int jx, jy, fx, fy;//지훈이와 불의 초기 위치를 위함
int countMax;
void bfsj(int jx, int jy, int count)
{
	queue<pair<int,pair<int, int>>> q;
	visited[jx][jy] = true;
	q.push({ jx,{jy,count } });
	while (!q.empty())
	{
		int tempx = q.front().first;
		int tempy = q.front().second.first;
		int count = q.front().second.second;
		ansj[tempx][tempy] = count;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int tx = tempx + vx[i];
			int ty = tempy + vy[i];
			if (tx<1 || tx>r || ty<1 || ty>c)
				continue;
			if (visited[tx][ty])
				continue;
			if (ansf[tx][ty] <=count+1)
				continue;
			if (arr[tx][ty] == '.')
			{
				visited[tx][ty] = true;
				q.push({ tx,{ty,count + 1} });
			}
			
		}

	}
}
void bfsf(int count)
{
	queue<pair<int, pair<int,int>>> fq;

	for (int i = 1; i <= r; i++)
	{
		for (int j = 1; j <= c; j++)
		{
			if (arr[i][j] == 'F')
			{
				visitedF[i][j] = true;
				fq.push({ i,{j,1 } });
			}
			if (arr[i][j] == '#')
			{
				visitedF[i][j] = true;
			}
			ansf[i][j] = 1000;
		}
	}
	while (!fq.empty())
	{
		int tempx = fq.front().first;
		int tempy = fq.front().second.first;
		int count = fq.front().second.second;
		ansf[tempx][tempy] = count;
		fq.pop();
		for (int i = 0; i < 4; i++)
		{
			int tx = tempx + vx[i];
			int ty = tempy + vy[i];
			if (tx<1 || tx>r || ty<1 || ty>c)
				continue;
			if (visitedF[tx][ty])
				continue;
			visitedF[tx][ty] = true;
			fq.push({ tx,{ty,count + 1} });
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> r >> c;
	for (int i = 1; i <= r; i++)
	{
		string a;
		cin >> a;
		for (int j = 0; j < c; j++)
		{
			arr[i][j + 1] = a[j];
			if (a[j] == 'J')
			{
				jx = i;
				jy = j + 1;
			}
		}
	}
	bfsf(1);
	bfsj(jx, jy, 1);
	vector<int> realAns;
	for (int i = 1; i <= r; i++)
	{
		for (int j = 1; j <= c; j++)
		{
			if ((i==1 || j==1|| i == r || j == c) && ansj[i][j]!=0)
			{
				realAns.push_back(ansj[i][j]);
			}
		}
	}
	if (realAns.empty())
	{
		cout<< "IMPOSSIBLE";
	}
	else
	{
		sort(realAns.begin(), realAns.end());
		cout << realAns[0];
	}
}

주의사항)

불이 움직이는 경로

일반적인 길 찾기 알고리즘과 같이 DFS를 이용해서 불이 갈 수 있는 경로를 계산해 두면 된다. 초기 값을 최대값인 1000으로 두어 추후 비교 시에 활용하는 방법을 사용했다.

 

지훈이가 움직이는 경로

불이 움직이는 경로를 확인하여 queue에 넣을지 넣지 않을 지 고려하여야 한다.

for (int i = 0; i < 4; i++)
{
    int tx = tempx + vx[i];
    int ty = tempy + vy[i];
    if (tx<1 || tx>r || ty<1 || ty>c)
    	continue;
    if (visited[tx][ty])
    	continue;
    if (ansf[tx][ty] <=count+1)
    	continue;
    if (arr[tx][ty] == '.')
    {
    	visited[tx][ty] = true;
	    q.push({ tx,{ty,count + 1} });
    }
}

1. 범위를 넘어 가는 곳은 continue를 사용하여 pass한다.

2. 방문한 곳은 재 방문하지 않는다.

3. 불이 지나간 곳의 값과 지훈이가 해당 위치에 도착할 값을 비교한다.

비교한 값이 불이 지나간 곳의 값보다 크거나 같으면 지훈이는 그곳을 지날 수 없다.

(이 경우 초반에 불이 움직이는 경로의 초기값을 큰 수로 초기화 하지 않으면, 추후 TC에서 오류가 발생한다)

4. 해당 위치에 들어갈 수 있는 값을 넣어준다.

 

Hidden Case

4 4
###F
#..#
#J.#
#..#

 

Ans: 2

(불이 움직이지 못하는 경우도 고려해야 한다. 이 case에서 앞서 언급한 불이 움직이는 경우의 초기값을 큰 수로 초기화 하지 않은 경우 "틀렸습니다."가 발생할 수 있다.)

 

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

 

Ans: 4

(출력 값은 가장 자리에서 가장 작은 값임을 생각하고, 이를 고려하여 코딩하였는지 확인할 수 있는 TC이다.)

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest