4179번: 불! [C++]

불! 

다국어

 

시간 제한              메모리 제한                                제출                                           정답                                맞힌 사람                        정답 비율

1 초

256 MB

32350

7238

4973

21.390%

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

 

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

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

예제 입력 1 복사

4 4
####
#JF#
#..#
#..#

예제 출력 1 복사

3

 

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

4179번: 불!

 

흐름

틀린 코드

#include <bits/stdc++.h>
using namespace std;

int r,c,visited[1004][1004], cnt, jcnt,fcnt;
char a[1004][1004];
vector<pair<int,int>> J,F;
pair<int,int> goal;

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

void bfs(int y, int x){
    visited[y][x]=1; cnt=987654321;
    queue<pair<int,int>> q;
    q.push({y,x});
    while(q.size()){
        tie(y,x)=q.front(); q.pop();
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny<0||nx<0||ny>=r||nx>=c||visited[ny][nx]||a[ny][nx]=='#'||a[ny][nx]=='F') continue;
            visited[ny][nx]=visited[y][x]+1;
            if (ny==0||nx==0||ny==r-1||nx==c-1){
                cnt = min(cnt, visited[ny][nx]);
                if(cnt==visited[ny][nx]) goal={ny,nx};
            } 
            q.push({ny,nx});
        }
    }
}
void bfs2(int y, int x){
    visited[y][x]=1; cnt=987654321;
    queue<pair<int,int>> q;
    q.push({y,x});
    while(q.size()){
        tie(y,x)=q.front(); q.pop();
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny<0||nx<0||ny>=r||nx>=c||visited[ny][nx]||a[ny][nx]=='#'||a[ny][nx]=='F') continue;
            visited[ny][nx]=visited[y][x]+1; 
            if (ny==goal.first&&nx==goal.second){
                cnt = min(cnt, visited[ny][nx]);
            } 
            q.push({ny,nx});
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력하기
    cin >> r >> c;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin >> a[i][j];
            if(a[i][j]=='J') J.push_back({i,j});
            if(a[i][j]=='F') F.push_back({i,j});
        }
    }
    //2-1. 지훈 - bfs 수행
    for(pair<int,int> p:J){
        bfs(p.first, p.second);
    }
    // 초기값일때
    if(cnt==987654321) {
        cout << "IMPOSSIBLE";
        return 0;
    }
    else jcnt=cnt;

    //초기화
    fill(&visited[0][0], &visited[0][0]+1004*1004,0);
    //2-2. 불 - bfs 수행
      for(pair<int,int> p:F){
        bfs2(p.first, p.second);
    }
    fcnt=cnt;

    //3. 출력하기
    if(jcnt>=fcnt) cout<<"IMPOSSIBLE";
    else cout << jcnt;

}

 

도착시간이 불보다 빠르기만 하면 될 줄 알았지만, 

중간에 불을 만나면 지훈이는 타버리고 만다.

 

체스게임을 하듯이 한칸씩 말을 움직여야한다.

불과 지훈이를 함께 움직일 수 있는 방법 찾기 => X: 최단경로는 이미 결정되어있으므로 불과 지훈의 블록마다 이동 시간 비교(누가 더 그 블록에 빨리 지나가는지) 하면 더 쉽다.

 

 

유의할 점

• 불은 여러개일수 있지만, 지훈이는 한명이다.
• 1부터 1000까지이므로 배열 범위는 1000이 아닌 1004정도로 하자.
• 불이 움직이는 곳은 불타고있다. 지훈은 불이 방문한 곳을 방문할 수 없다.
  • 지훈이 움직이는 위치와 불이 움직이는 위치를 시간순으로 따로 표시하여(bfs) 불이 먼저 타고있으면 지훈은 갈 수 없다.(경로비교)
  • 지훈 최단거리, 불 최단 거리를 블록마다 저장(visited 배열) -> 지훈은 블럭에서 불보다 앞서서 이동해야한다(거리 값의 크기가 작다.) 
  • 한 블록에서: 지훈 거리값 <불 거리값 인 곳만 가기(불이 오지않는 곳에 먼저 이동)
• 반례: 불이 없을때 
  • 만약 불이 없다면 불의 거리값은 0이되고 (visited배열의 초기값) 비교가 옳게 되지않으므로 불의 visited 배열의 초기값은 INF로 한다.
• 유의할점: 괄호 범위 주의하자!

선생님 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;
char a[1004][1004];
int n,m,sx,sy,dy[4]={-1,0,1,0}, dx[4]={0,1,0,-1}, ret,y,x;
int fire_check[1004][1004], person_check[1004][1004];

bool in(int a,int b){
    return 0<=a && a<n && 0<=b && b<m;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    queue<pair<int,int>> q;
    //1. 입력받기
    cin >> n >> m;
    fill(&fire_check[0][0], &fire_check[0][0]+1004*1004, INF); //초기화(사람이 항상 더 작야야함)

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> a[i][j];
            if(a[i][j]=='F'){ //불이면
                fire_check[i][j]=1; q.push({i,j});
            }
            else if(a[i][j]=='J'){ //지훈이면
                sy=i;sx=j;
            }
        }
    }
    //불 퍼지기
    while(q.size()){
        tie(y,x)=q.front(); q.pop();
        for(int i=0;i<4;i++){
            int ny = y+dy[i];
            int nx = x+dx[i];
            if(!in(ny,nx)) continue;
            if(fire_check[ny][nx]!=INF || a[ny][nx]=='#') continue; //불이 있거나 벽이 있으면 continue
            fire_check[ny][nx]=fire_check[y][x]+1; 
            q.push({ny,nx});
        }
    }
    //지훈 불로부터 도망가기
    person_check[sy][sx]=1;
    q.push({sy,sx});
    while(q.size()) {
        int y=q.front().first;
        int x=q.front().second;
        q.pop();
        if(x==m-1||y==n-1||x==0||y==0){ //벽에 닿으면 도망 성공
            ret=person_check[y][x];
            break;
        }
        for(int i=0;i<4;i++){
            int ny=y+dy[i];
            int nx=x+dx[i];
            if(!in(ny,nx)) continue;
            if(person_check[ny][nx]||a[ny][nx]=='#') continue; //간곳이거나 벽이면 continue
            if(fire_check[ny][nx]<=person_check[y][x]+1) continue; //이미 불이 났으면
            person_check[ny][nx]=person_check[y][x]+1;
            q.push({ny,nx});
        }
    }
    //3. 정답 출력
    if(ret!=0) cout<<ret<<"\n"; //탈출했다면
    else cout<<"IMPOSSIBLE\n";
    return 0;
    
}