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



bfs는 이번에 푼 문제가 거의 처음이여서 그런지, 실수가 있었습니다.


그냥 if문을 썼어야 됬는데, else if 를 써서 틀렸더라고요. if로 수정하니 잘 됬습니다.






처음엔 이렇게 풀었었습니다.

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
#include <iostream>
#include <queue>
using namespace std;
bool map[50][50] = {0};
 
void bfs(int height, int width);
 
 
 
int main(){
    ios_base::sync_with_stdio(false);
    int T, height, width, N,x,y;
    cin >> T;
    
    for(int i = 0 ; i < T; i++){
        cin >> width >> height;
        cin >> N;
 
        for(int i = 0; i < N; i++){
            cin >> x >> y;
            map[y][x] = 1;
        }
        
        bfs(height, width);
    }
    
    
}
 
void bfs(int height, int width){
 
    int count = 0;
    queue<pair<int,int>> q; //y,x
    
    
    for(int i = 0; i < height; i++){
        for(int j = 0; j < width; j++){
            
            if(map[i][j]){
                q.push({i,j});
                count +=1;
                map[i][j] = 0;
                
                while(!q.empty()){
                    int y = q.front().first;
                    int x = q.front().second;
                    q.pop();
                    if(y+1 < 50 && map[y+1][x]){
                            map[y+1][x] = 0; q.push({y+1,x});
                    }
                    if(y-1 >= 0 && map[y-1][x]){
                            map[y-1][x] = 0; q.push({y-1,x});
                    }
                    if(x+1 < 50 && map[y][x+1]){
                            map[y][x+1] = 0; q.push({y,x+1});
                    }
                    if(x-1 >= 0 && map[y][x-1]){
                            map[y][x-1] = 0; q.push({y,x-1});
                    }
                }
                
                
            }
            
        }
    }
    
    cout << count << endl;
}
cs


다 풀고 다른 분들 소스 보니, 상하좌우 방향 찾는 것을 깔끔하게 하는 것을 봤습니다.


그래서 수정해서 한번 더 제출 해보니

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
#include <iostream>
#include <queue>
using namespace std;
bool map[50][50] = {0};
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
void bfs(int height, int width);
 
 
 
int main(){
    ios_base::sync_with_stdio(false);
    int T, height, width, N,x,y;
    cin >> T;
    
    for(int i = 0 ; i < T; i++){
        cin >> width >> height;
        cin >> N;
 
        for(int i = 0; i < N; i++){
            cin >> x >> y;
            map[y][x] = 1;
        }
        
        bfs(height, width);
    }
    
    
}
 
void bfs(int height, int width){
 
    int count = 0;
    queue<pair<int,int>> q; //y,x
    
    
    for(int i = 0; i < height; i++){
        for(int j = 0; j < width; j++){
            
            if(map[i][j]){
                q.push({i,j});
                count +=1;
                map[i][j] = 0;
                
                while(!q.empty()){
                
                    for(int k=0;k<4;k++){
                        int y = q.front().first+dy[k];
                        int x = q.front().second + dx[k];
                        if(x <0 || x >= width || y < 0 || y >= height) continue;
                        if(map[y][x]){
                            map[y][x] = 0; q.push({y,x});
                        }
                    }
                    q.pop();
                    
                }
                
                
            }
            
        }
    }
    
    cout << count << endl;
}
cs

잘 되더라고요.

반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[Dp] 백준 11726 2xn타일링  (0) 2018.11.13
[bfs] 백준 2468 안전 영역  (0) 2018.11.13
백준 3015 오아시스 재결합  (0) 2018.11.10
백준 2294 (동전2)  (0) 2018.11.09
백준 2293 (동전1)  (0) 2018.11.07

+ Recent posts

티스토리툴바