백준 4179 불!

문제링크 : https://www.acmicpc.net/problem/4179

아이디어

• BFS를 사용해서 지훈이와 불을 각각 하나씩 이동해주자
• 이떄 지훈이가 밖으로 넘어가면 종료

시간복잡도 계산

• BFS(V+E)
  • V : O(RC)
  • E : O(RC*4)
  • 총합 : O(RC)

자료구조

• map[1000][1000]
• BFS queue<pair<int, int>>
  • 좌표 최대 1000
• 시간 t : 최대 1000

코드(C++)

#include <iostream>
#include <queue>
 
using namespace std;
typedef pair<int, int> pi2;
 
char map[1010][1010];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    queue<pi2> jihoon;
    queue<pi2> fire;
    
    int R,C; cin >> R >> C;
    for(int j=0; j<R; j++) {
        for(int i=0; i<C; i++) {
            cin >> map[j][i];
            if(map[j][i] == 'J') jihoon.push(make_pair(j,i));
            else if(map[j][i] == 'F') fire.push(make_pair(j,i));
        }
    }
    
    int t=0;
    while(1) {
        t++;
        // 지훈 먼저 이동
        int jsize = jihoon.size();
        if(jsize == 0) break;
        
        while(jsize--) {
            auto ej = jihoon.front(); jihoon.pop();
            int ey = ej.first;
            int ex = ej.second;
            
            // 만약 현재 위치가 불이라면 이동불가
            if(map[ey][ex] == 'F') continue;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
                // 탈출하면 종료
                if(!(ny>=0 && ny < R && nx >=0 && nx < C)) {
                    cout << t << '\n';
                    return 0;
                }
                
                // .일떄만 이동
                if(map[ny][nx] == '.' ) {
                    map[ny][nx] = 'J';
                    jihoon.push(make_pair(ny, nx));
                }
            }
            
        }
        
        // 불 이동
        int fsize = fire.size();
        while(fsize--) {
            auto ef = fire.front(); fire.pop();
            int ey = ef.first;
            int ex = ef.second;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
 
                if(ny>=0 && ny < R && nx >=0 && nx < C) {
                    if(map[ny][nx] == 'J' || map[ny][nx] == '.') {
                        map[ny][nx] = 'F';
                        fire.push(make_pair(ny, nx));
                    }
                }
            }
        }
        
        
        
    }
    
    cout << "IMPOSSIBLE";
    
    return 0;
}
 

문제유형

• BFS - 경찰과 도둑
  • 경찰은 쫓고, 도둑은 탈출
  • bfs로 맵을 인자로하면 메모리 차지가 너무크므로, 경찰, 도둑 좌표를 인자로