코딩 공부/백준

[백준][C++] 5427 불

김 정 환 2021. 3. 23. 23:35
반응형

www.acmicpc.net/problem/5427

 

5427번: 불

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에

www.acmicpc.net

 

 

 

알고리즘 종류

    - BFS

    - 구현

 

 

 

사고 과정

    - 매 초마다, 사건은 두 가지가 동시에 일어난다.

        1. 불이 움직인다.

        2. 상근이가 움직인다.

 

    - 불이 있고, 또는 불이 움직일 곳으로는 상근이가 갈 수 없다. 그리고 상근이가 있는 칸에 불이 오는 동시에 상근이가 움직인다. 이를 구현하기 위해서는 동시간 대에 불이 먼저 움직이면 된다.

        * 0초

 

        * 1초

            + 왼쪽은 불이 먼저 움직인 사건이다. 동시간 1초대에서 빨간색은 불이 움직이 곳이고 노란색 이건 불이다.

            + 오른쪽은 상근이가 움직인 사건이다. 

 

        * 2초

            + 왼쪽은 불이 먼저 움직인 사건이다.

            + 오른쪽은 상근이가 움직인 사건이다. 하늘색의 상근이는 문제에서 '상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.' 에 해당한다.

 

        * 정리하자면, 문제에서 제시된 조건을 충족하기 위해서는 동시간대에 불이 먼저 움직이고 상근이가 움직이면 된다. 알고리즘의 형태는 아래와 같이 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
while(조건){
 
    시간++;
 
    while(불의 Queue 크기){
        // 동작
    }
 
    while(상근의 Queue 크기){
        // 동작
    }
}
 
cs

 

 

 

구현(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <queue>
#include <cstring>
#define MAX 987654321
 
using namespace std;
 
 
int t, w, h;
 
char mat[1001][1001];
int sIsVisited[1001][1001];
int fIsVisited[1001][1001];
int dir[4][2= {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
queue<pair<intint> > sq;
queue<pair<intint> > fq;
 
bool isValid(int y, int x){
    return (y>=0 && y<h) && (x>=0 && x<w);
}
 
int bfs(){
 
    int time = 0;
    while(!sq.empty()){
        time++;
        
        // 불 이동  
        int fSize = fq.size();
        while(fSize--){
            int cy = fq.front().first;
            int cx = fq.front().second;
            fq.pop();
                
            for(int d=0; d<4; d++){
                int ny = cy + dir[d][0];
                int nx = cx + dir[d][1];
                    
                if(fIsVisited[ny][nx]) continue;
                if(!isValid(ny, nx)) continue;
                if(mat[ny][nx] == '#'continue;
                    
                fIsVisited[ny][nx] = 1;    
                fq.push({ny, nx});
            }    
        }
            
        // 상근이 이동  
        int sSize = sq.size();
        while(sSize--){
            int cy = sq.front().first;
            int cx = sq.front().second;
            sq.pop();
                
            for(int d=0; d<4; d++){
                int ny = cy + dir[d][0];
                int nx = cx + dir[d][1];
                    
                if(!isValid(ny, nx)) return time; // 상근이 탈출  
                    
                if(sIsVisited[ny][nx]) continue;
                if(mat[ny][nx] == '#'continue;
                if(fIsVisited[ny][nx]) continue;
                    
                sIsVisited[ny][nx] = 1;    
                sq.push({ny, nx});
            }
        }
    }
 
    return MAX;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> t;
    
    while(t--){
        
        memset(fIsVisited, 0sizeof(fIsVisited));
        memset(sIsVisited, 0sizeof(sIsVisited));
        memset(mat, 0sizeof(mat));
        while(!fq.empty()) fq.pop();
        while(!sq.empty()) sq.pop();
        
        cin >> w >> h;
        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                cin >> mat[i][j];
                if(mat[i][j] == '@'){
                    sq.push({i, j});
                    sIsVisited[i][j] = 1;
                } 
                if(mat[i][j] == '*') {
                    fq.push({i, j});
                    fIsVisited[i][j] = 1;
                }
            }
        }
        
        int res = bfs();
        if(res == MAX) cout << "IMPOSSIBLE" << endl;
        else cout << res << endl;
        
    }
}
 
cs

 

 

 

시행착오

    - 목적지에 도착하면 바로 종료하고 값을 반환하면 되는데 본인은 한 바퀴 더 돌려서 시작점에서 반환하려고 하는 습관이 있었다. 그러면 중간에 목적지에 도착한 값이 한 바퀴를 돌 때 여러 조건들을 통과한다는 보장은 없다. 따라서 목적지에 도착하면 바로 답을 반환하자. 

 

    - 무슨 말인가...하면

더보기

아래와 같이 작성해야 되는데

while(sSize--){

            int cy = sq.front().first;

            int cx = sq.front().second;

            sq.pop();

                

            for(int d=0; d<4; d++){

                int ny = cy + dir[d][0];

                int nx = cx + dir[d][1];

                    

                if(!isValid(ny, nx)) return time; // 상근이 탈출  

                    

                if(sIsVisited[ny][nx]) continue;

                if(mat[ny][nx] == '#'continue;

                if(fIsVisited[ny][nx]) continue;

                    

                sIsVisited[ny][nx] = 1;    

                sq.push({ny, nx});

            }

}

 

아래와 같이 작성했었다.

// 상근이 이동  

        int sSize = sq.size();

        while(sSize--){

            int cy = sq.front().first;

            int cx = sq.front().second;

            sq.pop();

            

            if(!isValid(cy, cx)) return time; // 상근이 탈출  

                

            for(int d=0; d<4; d++){

                int ny = cy + dir[d][0];

                int nx = cx + dir[d][1];

                    

                if(sIsVisited[ny][nx]) continue;

                if(mat[ny][nx] == '#'continue;

                if(fIsVisited[ny][nx]) continue;

                    

                sIsVisited[ny][nx] = 1;    

                sq.push({ny, nx});

            }

        }

 

반응형

'코딩 공부 > 백준' 카테고리의 다른 글

[백준][C++] 16929 Two Dots  (0) 2021.03.26
[백준][C++] 2234 성곽  (0) 2021.03.24
[백준][C++] 17836 공주님을 구해라!  (0) 2021.03.23
[백준][C++] 2024 선분 덮기  (0) 2021.03.23
[백준][C++] 18809 gaaaaaaaaaarden  (0) 2021.03.20