본문 바로가기
Problem Solving/BOJ

백준 1012 유기농 배추 풀이 C++

by chuckolet 2019. 1. 28.

Introduction


그래프와 DFS 관련 문제입니다.

저는 가뜩이나 공간 지각 능력이 부족한데 이 문제는 제가 거의 처음 풀어본 그래프, DFS 문제이면서 평소에 익숙한 행렬(row, col) 방식이 아닌 좌표평면(x,y) 방식으로 배추밭의 길이가 주어져서 머리 속에서 그림으로 변환하여 이해하는데 굉장히 애를 먹었습니다. 

main함수 자체는 변수를 입력 받고, 배추가 심어져 있는 부분을 1로 변경해주는 비교적 간단한 작업인데 입력 받아온 값을 dfs 함수에 보내고 탐색하는 과정을 짤 때 가로, 세로와 row, column이 머리 속에서 뒤엉켜서 몇 번이나 혼자 짜는 것에 실패했습니다. 그래서 처음에는 둘 다 사용했던 단위를 제가 더 편한 행렬 방식으로 통일해서 해결할 수 있었습니다. 

아래 코드를 보시면 M, N 자체는 각각 가로, 세로를 의미하므로 순서대로 받았지만, row, col을 의미하는 r, c는 반대로 입력 받은 것을 확인 할 수 있습니다. 또한 모든 행렬 값을 순회 하는 역할을 하는 이중 for문에서도 M과 N의 순서를 바꿔서 row, col 순서로 순회하는 것을 확인 할 수 있습니다. 그리고 이 순서 그대로 dfs 함수에 r, c를 넘겨주어서 dfs 함수 내에서는 아무 고민 없이 row, col으로 생각하면서 문제를 해결할 수 있었습니다. dirR, dirC는 각각 nextR, nextC에 더해주어서 동서남북으로 탐색하기 위해 row, col 방향을 1씩 변경해주는 변수이며, main 함수에서 처음 1을 만났을 때 warm++ 해주고 그 1과 이어져 있는 다른 1들은 dfs를 재귀로 돌려서 모두 0으로 바꿔주는 방식으로 코딩했습니다. 다른분 중에는 visted[][] 배열을 따로 만들어서 그걸로 계산하시는 분도 있었는데 메모리가 넉넉하다면 그 방식도 괜찮은 방법이라고 생각합니다.

아마 이 문제가 잘 풀리지 않으시면 컴퓨터 상의 좌표 시스템이나 행렬 or DFS의 재귀 동작 중에서 명쾌하게 이해하지 못한 부분이 있지 않은가 생각해보시고 관련 분야 공부를 하신 뒤에 풀면 좀 더 쉽게 이해되실 것이라 생각합니다. 

Image result for 컴퓨터 좌표

궁금한 점 있으시면 답글 남겨주세요!


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
#include <iostream>
#include <vector>
using namespace std;
 
#define MAX 51
int M, N, K;
int farm[MAX][MAX];
 
// 동서남북
int dirR[4]{0, 0, 1, -1};
int dirC[4]{1, -1, 0, 0};
 
void dfs(int r, int c) {
    farm[r][c] = 0; // 이미 방문한 곳은 0으로 변경해서 중복 방문 방지
 
    for(int i=0; i<4; i++) {
        int nextR = r + dirR[i];
        int nextC = c + dirC[i];
 
        // 예외처리
        if(nextR < 0 || nextR > N || nextC < 0 || nextC > M) continue;
        if(farm[nextR][nextC] == 0) continue;
        dfs(nextR, nextC);
    }
}
 
int main() {
    int T;
    cin >> T;
 
    while(T--) {
        int warm = 0;
        cin >> M >> N >> K;
 
        for(int i=0; i<K; i++) {
            int r, c;
            cin >> c >> r;
            farm[r][c] = 1;
        }
 
        for(int i=0; i<N; i++) {
            for(int j = 0; j < M; j++) {
                if(farm[i][j] != 0) {
                    // print all
//                    for (int i = 0; i < N; i++) {
//                        for (int j = 0; j < M; j++) {
//                            cout << farm[i][j] << " ";
//                        }
//                        cout << "\n";
//                    }
//                    cout << "\n";
                    warm++;
                    dfs(i, j);
                }
            }
        }
        cout << warm << "\n";
    }
}
cs

주석 처리된 print all 부분의 주석을 해제 하시면 아래와 같은 DFS의 진행과정을 확인 하실 수 있습니다.

1 1 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 1 1 0 0 0 1 1 1 
0 0 0 0 1 0 0 1 1 1 
0 0 0 0 0 0 0 1 1 1 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 1 1 0 0 0 1 1 1 
0 0 0 0 1 0 0 1 1 1 
0 0 0 0 0 0 0 1 1 1 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 1 1 0 0 0 1 1 1 
0 0 0 0 1 0 0 1 1 1 
0 0 0 0 0 0 0 1 1 1 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 1 1 
0 0 0 0 1 0 0 1 1 1 
0 0 0 0 0 0 0 1 1 1 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0

References

https://kks227.blog.me/220787042377?Redirect=Log&from=postView

https://dongyeollee.github.io/2018/07/09/Al/1012/


제 글이 도움이 되셨다면 간단하게 '공감', '댓글' 부탁드립니다!



저작자표시 비영리 변경금지

'Problem Solving > BOJ' 카테고리의 다른 글

백준 11718 그대로 출력하기 C++  (0) 2019.02.02
백준 1918 후위 연산자 풀이 C++  (0) 2019.01.20
백준 문제 풀이, PS 관련 사이트 모음  (0) 2018.12.28
백준 11718번 그대로 출력하기 풀이 Python  (0) 2018.11.23
백준 10929번 SHA-224 풀이 Python  (0) 2018.11.23

관련글

댓글

티스토리툴바