[백준] 4179번 불!

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이난 공간

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

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

 

 

이 문제는 bfs를 두 번 돌리는 문제다.  (dfs도 될지도 모른다.)

문제를 읽어보면 지훈이는 불의 이동에 영향을 받으며 이동하고 있다.

그러니까 결국 불의 이동 경로를 구하고 그 다음에 지훈이의 경로를 구해주면된다.

만약, 불의 이동 경로가 지훈이의 경로보다 작다면 그곳으로 갈 수 없다.

 

원래 목적은 메소드 2개를 이용해서 풀려고 했는데 아직 경험 부족인지,

원래 안되는 건지는 모르겠지만 아무튼 나는 되지 않았다. 나중에 메소드사용해서 풀어보도록 시도해봐야겠다.

#include <bits/stdc++.h>
using namespace std;
char dist[1010][1010];
int R,C;
int fire[1010][1010];
int jhun[1010][1010];

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


int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  
  cin >> R >> C;

  for(int i = 0; i<R;i++) {
    for(int j = 0; j<C;j++) {
      cin >> dist[i][j];
      fire[i][j] = -1;
      jhun[i][j] = -1;
    }
  }

  // 불과 지훈이의 초기값 설정
  queue<pair<int,int>> q1;
  queue<pair<int,int>> q2;
 
  for(int i = 0;i<R;i++) {
    for(int j = 0; j<C;j++) {
      if (dist[i][j] == 'F') {
          q1.push({i,j});
          fire[i][j]++;
      }
      if (dist[i][j] == 'J') {
          q2.push({i,j});
          jhun[i][j]++;
      }
    }
  }

  // 불의 이동
  while(!q1.empty()) {
    pair<int,int> cu = q1.front();
    q1.pop();
    for(int i = 0;i<4;i++) {
      int nx = cu.first + dx[i];
      int ny = cu.second + dy[i];

      if (nx < 0 || R <= nx || ny  < 0 || C <= ny) continue;

      if (dist[nx][ny] == '#') continue;
      if (fire[nx][ny] > -1) continue;
      q1.push({nx,ny});
      fire[nx][ny] = fire[cu.first][cu.second] + 1;
    }
  }

  // 지훈이의 이동
  while(!q2.empty()) {
    pair<int,int> cu = q2.front();
    q2.pop();
    for(int i = 0; i < 4; i++) {
      int nx = cu.first + dx[i];
      int ny = cu.second + dy[i];

      if (nx < 0 || R <= nx || ny  < 0 || C <= ny) {
       cout << jhun[cu.first][cu.second] +1<< "\n";
       return 0;

      }

      if (dist[nx][ny] == '#') continue;
      if (jhun[nx][ny] > -1) continue;

      if (fire[nx][ny] > -1 && fire[nx][ny] <= jhun[cu.first][cu.second]+1) continue;

      q2.push({nx,ny});
      jhun[nx][ny] = jhun[cu.first][cu.second] + 1;
    }
  }

  cout << "IMPOSSIBLE";

} 

일단 -1로 초기화를 시켜줘야한다. 굳이 초기화 시킬 필요는 없지만, 초기화를 시키면 편하기 때문에 초기화를 시켜주었다.

 

또.... 탈출 조건이 지훈이가 이동경로를 벗어나는 것이기 때문에 

이런식으로 하였다. 

 

마지막으로 -1보다 큰 값을 작성하는 이유는 이게 바로 경로 표시다. 

보통은 boolean값으로 하는데, 이 문제에서는 굳이 필요없을 것 같아 추가하지 않았다.

 

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

int r, c;
string s[1000];
bool vj[1000][1000], vf[1000][1000];

struct A {
	int y, x;
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> r >> c;
	int i, j;

	queue<A> qj, qf;
	for (i = 0; i < r; i++)
	{
		cin >> s[i];
		for (j = 0; j < c; j++)
		{
			if (s[i][j] == 'J')
			{
				vj[i][j] = true;
				qj.push({ i, j });
			}
			if (s[i][j] == 'F')
			{
				vf[i][j] = true;
				s[i][j] = '#';
				qf.push({ i, j });
			}
		}
	}

	int dy[]{ 0,0,1,-1 };
	int dx[]{ 1,-1,0,0 };
	int t = 1;
	
	while (!qj.empty())
	{
		for (j = (int)qf.size(); j; j--)
		{
			int y = qf.front().y;
			int x = qf.front().x;
			qf.pop();

			for (i = 0; i < 4; i++)
			{
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || ny >= r || nx < 0 || nx >= c || vf[ny][nx] || s[ny][nx] == '#')
					continue;
				vf[ny][nx] = true;
				s[ny][nx] = '#';
				qf.push({ ny, nx });
			}
		}

		for (j = (int)qj.size(); j; j--)
		{
			int y = qj.front().y;
			int x = qj.front().x;
			qj.pop();

			for (i = 0; i < 4; i++)
			{
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || ny >= r || nx < 0 || nx >= c)
				{
					cout << t;
					return 0;
				}
				else if (vj[ny][nx] || s[ny][nx] == '#')
					continue;

				vj[ny][nx] = true;
				qj.push({ ny, nx });
			}
		}

		t++;
	}

	cout << "IMPOSSIBLE";
}

 

확실하지 않으면 메소드를 만드는것 보다 그냥 만드는게 훨씬 좋다.!