DFS 문제 분석-1(두더지, 섬, 배추...)

DFS의 비슷한 문제 유형을 풀어보고 분석해보자.

1. 두더지 문제 분석

#include <stdio.h>
 
int matrix[101][101];//matrix 초기 사이즈를 크게크게 잡자 1~5정도 더 크게.
int homeSize[101];
int homeCnt;
int matrix_size;
 
/*
rangeOverCheck
깊이우선탐색을 하면서, 노드(배열의 각각 요소)의 범위를 넘지 않도록 check한다.
i와 j는 행과 열의 값.
*/
int rangeOverCheck(int i, int j) {
    if (i > matrix_size || i<0 || j>matrix_size || j < 0)
        return 0;
    
    return 1;
}
/*
DOTHEJI_HOME_DFS
깊이우선탐색의 함수. 탐색한 노드는 2로 설정한다.
*/
void DOTHEJI_HOME_DFS(int i, int j) {
    
    matrix[i][j] = 2;//matrix[i][j] = 0으로 설정하면 TestCase를 돌면서 초기화를 하지 않아도 된다.
    homeSize[homeCnt]++;
 
    //배열, 반복문을 이욯해서 탐색 할 수 있다.
    if (rangeOverCheck(i, j + 1) == 1 && matrix[i][j + 1] == 1) {
        DOTHEJI_HOME_DFS(i, j + 1);
    }
 
    if (rangeOverCheck(i, j - 1) == 1 && matrix[i][j - 1] == 1) {
        DOTHEJI_HOME_DFS(i, j - 1);
    }
 
    if (rangeOverCheck(i - 1, j) == 1 && matrix[i - 1][j] == 1) {
        DOTHEJI_HOME_DFS(i - 1, j);
    }
 
    if (rangeOverCheck(i + 1, j) == 1 && matrix[i + 1][j] == 1) {
        DOTHEJI_HOME_DFS(i + 1, j);
    }
}
 
void bubbleSort() {
    
    for (int i = 0; i < homeCnt - 1; ++i) {//내가 왜 -1을 안썼을까...????
        for (int j = 0; j < homeCnt - i - 1; ++j) {
            if (homeSize[j] > homeSize[j + 1]){
                int temp = homeSize[j];
                homeSize[j] = homeSize[j + 1];
                homeSize[j + 1] = temp;
            }
        }
    }
}
 
int main(void) {
    
    scanf("%d", &matrix_size);
 
    for (int i = 0; i < matrix_size; ++i) {
        for (int j = 0; j < matrix_size; ++j) {
            scanf("%1d", &matrix[i][j]);//%1d로 받아서 띄어쓰기 없이 한번에 쓰자.
        }
    }
 
    /*
    (i,j)==(0,0)부터 돌면서 1인 부분이 나오면 탐색을 한다. 탐색횟수==집의 수.
    */
    for (int i = 0; i < matrix_size; ++i) {
        for (int j = 0; j < matrix_size; ++j) {
            if (matrix[i][j] == 1) {
                //homeCnt++ 정렬할때 많이 다르다.
                DOTHEJI_HOME_DFS(i, j);
                homeCnt++;
            }
        }
    }
 
    bubbleSort();
 
    printf("%d\n", homeCnt);
 
    for (int i = 0; i < homeCnt; ++i)
        printf("%d\n", homeSize[i]);
    
    return 0;
}

23번 줄에 있는 DOTHEJI_HOME_DFS를 다음과 같이 간단하게 바꿀 수 있다.

int row[4] = { -1,0,1,0 };
int col[4] = { 0,-1,0,1 };
 
void DOTHEJI_HOME_DFS(int i, int j) {
 
    matrix[i][j] = 2;
    homeSize[homeCnt]++;
 
 
    for (int a = 0; a < 4; ++i) {
        if (rangeOverCheck(i + row[a], j + col[a]) && matrix[i + row[a]][j + col[a]])
            DOTHEJI_HOME_DFS(i + row[a], j + col[a]);
    }
}

row와 cow를 설정한 방법이다.

2. 섬의 개수 문제 분석(boj.kr/4963)

#include <stdio.h>
 
#define MAX_ISLAND 55//size무조건 주어진 값보다 크게하기.
 
int row[8] = { -1,0,1,1,1,0,-1,-1 };//row 행i 
int col[8] = { -1,-1,-1,0,1,1,1,0 };//col 열j
 
int island[MAX_ISLAND][MAX_ISLAND];
int w, h;
 
/*
islandInit
testcase가 돌면서 새롭게 입력하기 전에, 그 전에 있던 배열을 초기화 해야한다.
*/
void islandInit() {
    for (int i = 0; i < MAX_ISLAND; ++i) {
        for (int j = 0; j < MAX_ISLAND; ++j) {
            island[i][j] = 0;
        }
    }
}
/*
DFS가 돌기위한 제한조건을 설정한다.
*/
int rangeOverCheck(int i, int j) {
    if (i > w || i<0 || j>h || j < 0)
        return 0;
 
    return 1;
}
 
/*
Island_DFS
DFS함수.
*/
void Island_DFS(int i, int j) {
    
    island[i][j] = 2;//=0으로 처리하면 초기화를 할 필요가없음.
    
    for (int a = 0; a < 8; ++a) {//제어변수를 잘 대입해주자...a로 설정해야지...
        if (rangeOverCheck(i + row[a], j + col[a]) == 1 &&
            island[i + row[a]][j + col[a]] == 1)
            Island_DFS(i + row[a], j + col[a]);
    }
}
 
int main(void) {
    
    w = 1, h = 1;//안해주면 while문 안돌아간다. 문제 조건상.
    
    int w1 = 1, h1 = 1;
 
    while (w1 != 0 && h1 != 0) {
        int cnt = 0;
        scanf("%d %d", &w1, &h1); 
 
        w = h1, h = w1;//행렬과 너비,높이의 i,j가 서로 다르다.. 여기서 낚였다..헤헤
 
        if (w1 == 0 && h1 == 0)
            return;//중간에 scanf때문에.
 
        for (int i = 0; i < w; ++i) {
            for (int j = 0; j < h; ++j) {
                scanf("%1d", &island[i][j]);
            }
        }
        
        for (int i = 0; i < w; ++i) {
            for (int j = 0; j < h; ++j) {            
                if (island[i][j] == 1) {
                    Island_DFS(i, j);
                    cnt++;// DFS가 돈 횟수 == 섬 한 덩어리 단위 개수.
                }
            }
        }
 
        printf("%d\n", cnt);
        
        islandInit();//중요!!!
        cnt = 0;
 
    }
 
    return 0;
}

3. 유기농 배추 문제 분석(boj.kr/1012)

#include <stdio.h>
 
#define BOT_SIZE 51//사이즈 무조건 더 추가하기. 가끔 여기서 틀린다.
 
int bot[BOT_SIZE][BOT_SIZE];
 
int M, N, K;
 
void botGaraupki(void) {//밭 갈아엎어야함, 초기화하기.
    for (int i = 0; i < BOT_SIZE; ++i) {
        for (int j = 0; j < BOT_SIZE; ++j)
            bot[i][j] = 0;
    }
}
 
int rangeOverCheck(int i, int j) {
    if (i > M || i<0 || j>N || j < 0)
        return 0;
 
    return 1;
}
 
void baechu_worm_DFS(int i, int j) {
 
    bot[i][j] = 2;//0으로 초기화하면 간단해진다.
    //포문으로바꾸기(배열로바꾸기)
 
    //직관적으로 읽기 쉽다. 하지만 배열을 이용하는게 더 깔끔하다.
    if (rangeOverCheck(i, j + 1) == 1 && bot[i][j + 1] == 1) 
        baechu_worm_DFS(i, j + 1);
 
    if (rangeOverCheck(i, j - 1) == 1 && bot[i][j - 1] == 1) 
        baechu_worm_DFS(i, j - 1);
 
    if (rangeOverCheck(i - 1, j) == 1 && bot[i - 1][j] == 1) 
        baechu_worm_DFS(i - 1, j);
 
    if (rangeOverCheck(i + 1, j) == 1 && bot[i + 1][j] == 1) 
        baechu_worm_DFS(i + 1, j);
 
}
 
int main(void) {
    int testCase;
    int a, b;
 
    scanf("%d", &testCase);
 
    for (int i = 0; i < testCase; ++i) {
        int cnt = 0;
 
        scanf("%d %d %d", &M, &N, &K);
 
        for (int j = 0; j < K; ++j) {
            scanf("%d %d", &a, &b);
            bot[a][b] = 1;
        }
 
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j)
                if (bot[i][j] == 1) {//1일때 돌린다 하지만 탐색한 노드는 2로 바꿔준다.
                    baechu_worm_DFS(i, j);
                    cnt++;
                }
        }
 
        printf("%d\n", cnt);
        cnt = 0;
 
        botGaraupki();
    }
 
    return 0;
}

사실 이쯤되면 거의 3개다 같은 문제이다...