[ C++ ] #4179 불!

 

흠..쉬울것같았는데 은근 고민스럽다..!

일단 미로문제니까 BFS로 풀자!

 

먼저 진호의 위치와 불의 위치를 파악하고,

진호의 위치로부터 가장자리로 가는 최단거리를 구한다.

최단거리를 구하는 방법은 check판에 이 자리까지 오는데 걸린거리를 기록하면서 나중에 최대값을 찾으면 될 것 같다.

 

불이랑 만나는지는 최단거리 루트를 구하고 생각할지, 아니면 BFS하면서 같이 구할지 고민하다가

fire배열을 만들어서 BFS업데이트할때 같이 업데이트해가면서 비교해봐야겠다고 생각했다. 

 

계속 어떤 케이스는 되고 어떤케이스는 안되고 해서

오류를 하나하나 고쳐나갔다.

 

근데 이제 웬만하면 모든케이스가 다 되는데...

너무 억울한데..도대체 뭐때문에 안되는지 모르겠다ㅠㅠ

---

일단 내 코드는 차차 고민해보는걸로하고..!

다른 아이디어를  발견했다.

불의 BFS를 돌려서 각 칸에 도달하는데 얼마나 걸리는지 구하고,

그 다음의 지훈이의 BFS를 돌려서 그 길을 지나갈 수 있는지 계산하는 것이다.

---

밤에 새로운 아이디어로 다시 코드를 짜보려고했지만

원래의 내 코드에서 해결봤다!!

최소 거리를 구할 때, min을 100으로 설정하고 최소값을 탐색하고도 min이 100이면 길이 없는걸로 판단하고

IMPOSSIBLE를 출력해버렸다.

하지만 내가 고려하지 못한건 거리가 100인경우..! 그래서 난 100을 10000으로 바꿨더니 해결됐다!

 

이 별거 아닌걸로 끙끙거렸다니!!

 

//내코드

#include<iostream>
#include<string>
#include<queue>
#include<vector>

using namespace std;

char miro[1001][1001];  //미로
int check[1001][1001];  //방문 및 거리 체크
int fire[1001][1001];  //불 퍼지기

int main() {

	int R, C;
	int num=0,fre=0,n=1,f=0; //퍼질 수 있는 불개수
	cin >> R >> C;
	int Jx=0, Jy=0, Fx=0, Fy=0;
	int dx[4] = {0,1,0,-1};
	int dy[4] = { 1,0,-1,0 };
	queue<pair<int, int>> Q;
	queue<pair<int, int>> F;

	string a;
	for (int i = 0; i < R; i++) {
		cin >>miro[i];
	}

	//진호,불 찾기
	for (int i = 0; i < R; i++) {
		for (int j = 0; j< C; j++) {
			check[i][j] = -1;
			if (miro[i][j] == 'J') {
				Q.push({ i,j });
				check[i][j] = 0;
				//Jx = i; Jy = j;
			}else if (miro[i][j] == 'F') {
				F.push({ i,j });
				fire[i][j] = 1;
				fre++;
			}
		}
	}
	num = fre;
	fre = 0;


	//BFS
	while (!Q.empty()) {

		//불퍼지기
		for (int i = 0; i < num; i++) {
			pair<int, int> FC = F.front();
			F.pop();

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

				if (nx < 0 || ny < 0 || nx >= C || nx >= R) continue;
				if (fire[nx][ny] == 1 || miro[nx][ny] != '.')continue;

				F.push({ nx,ny });
				fire[nx][ny] = 1;
				fre++;
				//cout << "F : " << nx << " , " << ny << " : " << num << endl;
			}
		}
		num = fre;
		fre = 0;
		

		//길찾기

		for (int j = 0; j < n; j++) {

			pair<int, int> Cu = Q.front();
			Q.pop();

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

				if (nx < 0 || ny < 0 || ny>  C - 1 || nx > R - 1) continue;
				if (check[nx][ny] > 1 || miro[nx][ny] != '.') continue;
				if (fire[nx][ny] == 1) continue;

				Q.push({ nx,ny });
				miro[nx][ny] = 1;
				if ((check[Cu.first][Cu.second] + 1) < check[nx][ny] || check[nx][ny] == -1)
					check[nx][ny] = check[Cu.first][Cu.second] + 1;
				f++;
				//cout << "C : " << nx << " , " << ny << " : " << check[nx][ny] << endl;
			}
		}

		n = f;
		f = 0;
	}

	//최단거리 찾기

	int min = 100000;
	for (int i = 0; i < R; i++) {  //왼쪽 오른쪽 가장자리 확인
		if (min > check[i][0]&&check[i][0]!=-1) min = check[i][0];
		if (min > check[i][C - 1] && check[i][C - 1] != -1) min = check[i][C - 1];
	}
	for (int i = 0; i < C; i++) {  //위아래 가장자리 확인
		if (min > check[0][i] && check[0][i] != -1) min = check[0][i];
		if (min >check[R-1][i] && check[R - 1][i] != -1) min = check[R - 1][i];
	}

	if(min == 100000 ||min==-1){
		cout << "IMPOSSIBLE";
	}else cout << min+1;
}

 

 

공부를 위해 다른 솔루션도 공부해봐야겠다!

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[1002];
int dist1[1002][1002]; // 불의 전파 시간
int dist2[1002][1002]; // 지훈이의 이동 시간
int n, m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++){  //-1로 채우기
    fill(dist1[i], dist1[i]+m, -1);
    fill(dist2[i], dist2[i]+m, -1);    
  }
  for(int i = 0; i < n; i++)
    cin >> board[i];  
  queue<pair<int,int> > Q1;
  queue<pair<int,int> > Q2;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; 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;
      }
    }
  }
  
  // 불에 대한 BFS
  while(!Q1.empty()){
    auto cur = Q1.front(); Q1.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue; 
      dist1[nx][ny] = dist1[cur.X][cur.Y]+1;
      Q1.push({nx,ny});
    }
  }

  // 지훈이에 대한 BFS
  while(!Q2.empty()){
    auto cur = Q2.front(); Q2.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m){ // 범위를 벗어났다는 것은 탈출에 성공했다는 의미. 큐에 거리 순으로 들어가므로 최초에 탈출한 시간을 출력하면 됨.
        cout << dist2[cur.X][cur.Y]+1; 
        return 0;
      }
      if(dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
      if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y]+1) continue; // 불의 전파 시간을 조건에 추가
      dist2[nx][ny] = dist2[cur.X][cur.Y]+1;
      Q2.push({nx,ny});
    }
  }
  
  cout << "IMPOSSIBLE"; // 여기에 도달했다는 것은 탈출에 실패했음을 의미.
}