[백준] 1012번: 유기농 배추 (C++)

 

어제 코테 스터디에서 DFS와 BFS에 대해 공부한 후

혼자서 풀어보는 첫 문제

DFS 와 BFS 너무 어렵습니다..

개념은 이해가 가지만 정작 코드로 짤 때 

빼먹는 부분도 많고, 변수도 신중히 써야하고

아직 코딩 경험이 부족한가 봅니다

제 부족한 지식을 채워준 아래 블로그를 참고 했습니다

[백준] 1012. 유기농 배추 풀이 (C++) (tistory.com)

 

테스트 케이스가 한 번인 경우에는 상관 없지만

테스트 케이스가 두 번 이상일 때는 입력 매핑 값도 두 번 받지만

방문 여부를 나타내는 배열도 전부 false로 바꿔놓아야 하는 것을 잊으면 안된다!

 

그리고 dfs는 일단 재귀로 구현하는 것이 아직까진 쉽다

물론 재귀 자체도 익숙하지 않아 애를 많이 먹긴 하지만..

 

그리고 2차원 이상의 배열을 사용해야 할 때

변수가 꼬이는 문제도 빈번하다

dfs 함수에서 x 와 y를 반대로 받아버리면 main 함수에서는 순서대로 작성하면 되는데

그걸 잊어서 main에서도 반대로 쓰곤 했다 하하..

 

2차원 배열도 헷갈려서 찾아봤다

아래와 같은 경우 길이가 5인 배열이 3개인 경우이다

3이 먼저고 5가 먼저면 (3,5) 크기인가 싶다가도 헷갈리면 안된다!

int arr[3][5] = {{1,2,3,4,5}, {1,2,3,4,5}, {1,2,3,4,5}};

 

그래서 위의 블로그를 거의 한줄한줄 보다시피 한 코드이다

// baekjoon 1012

#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
using namespace std;

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}

int arr[51][51];
bool visited[51][51] ;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int N, M, cabbage;

bool dfs(int current_y, int current_x){
    
    if(visited[current_y][current_x]){
        return false;
    }
    
    visited[current_y][current_x] = true;
    
    for(int i = 0; i < 4; i++){
        int next_y = current_y + dy[i];
        int next_x = current_x + dx[i];
        
        if((next_y >= 0 && next_x >= 0) && (next_y < N && next_x < M) && arr[next_y][next_x]){
            dfs(next_y, next_x);
        }
    }
    return true;
}


int main(){
    init();
    
    int t;
    cin >> t;
    
    for(int i = 0; i < t; i++){
        cin >> M >> N >> cabbage;
        
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                arr[i][j] = 0;
                visited[i][j] = false;
            }
        }
        
        for(int j = 0; j < cabbage; j++){
            int x, y;
            cin >> x >> y;
            arr[y][x] = 1;
        }
        
        int count = 0;
        
        for(int j = 0; j < N; j++){
            for(int k = 0; k < M; k++){
                if(arr[j][k] && !visited[j][k]){
                    if(dfs(j, k)){
                        count++;
                    }
                }
            }
        }
        
        cout << count << '\n';
    }
}