DFS 문제 분석-3(영역구하기, 음식물 피하기)

1. 영역구하기 문제 분석(boj.kr/2583)

#include <stdio.h>
 
#define MAX_SIZE 101
 
int paper[MAX_SIZE][MAX_SIZE];
int M, N, K;
int row[4] = { -1,0,1,0 };
int col[4] = { 0,-1,0,1 };
int area[MAX_SIZE];
int Area_cnt, djtArea;
 
int checkRangeOver(int i, int j) {
 
    return !(i < 1 || j<0 || i>M || j > N - 1) ? 1 : 0;
    
}
 
int paper_DFS(int i, int j) {
 
    paper[i][j] = 2;
 
    for (int a = 0; a < 4; ++a) {
        int row_y = i + row[a];
        int col_x = j + col[a];
 
        if (checkRangeOver(row_y, col_x) && paper[row_y][col_x] == 0) {
            paper_DFS(row_y, col_x);
            Area_cnt++;
        }
    }
    return Area_cnt;
}
 
void bubbleSort(void) {
 
    for (int i = 0; i < djtArea - 1; ++i) {
        for (int j = 0; j < djtArea - 1 - i; ++j) {
            if (area[j] > area[j + 1]) {
                int temp = 0;
                temp = area[j];
                area[j] = area[j + 1];
                area[j + 1] = temp;
            }
        }
    }
}
 
int main(void) {
 
    scanf("%d %d %d", &M, &N, &K);
 
    for (int k = 0; k < K; ++k) {
 
        int start_x = 0, start_y = 0;
        int finish_x = 0, finish_y = 0;
        int y1, y2;
 
        scanf("%d %d %d %d", &start_x, &start_y, &finish_x, &finish_y);
 
        finish_x--, finish_y--;
 
        y1 = M - start_y, y2 = M - finish_y;
 
        if (M - start_y > M - finish_y) {
            y1 = M - finish_y;
            y2 = M - start_y;
        }
 
        for (int i = y1; i <= y2; ++i) {
            for (int j = start_x; j <= finish_x; ++j) {
                paper[i][j] = 1;
            }
        }
    }
 
    for (int i = 1; i <= M; ++i) {
        for (int j = 0; j < N; ++j) {
            if (paper[i][j] == 0) {
                Area_cnt = 1;
                area[djtArea++] = paper_DFS(i, j);
            }
        }
    }
    bubbleSort();
 
    printf("%d\n", djtArea);
 
    for (int i = 0; i < djtArea; ++i) {
        printf("%d ", area[i]);
    }
    printf("\n");
 
    return 0;
}

이 문제의 핵심은, scanf를 어떻게, 받는지의 문제이다. DFS의 코드는 같다고 보면 된다.

C언어에서 (0,0)의 위치는 왼쪽 상단인데, 이 문제에서 (0,0)의 기준이 왼쪽 아래, 마치 xy좌표평면처럼 입력이 되었다. 그래서, 입력된 좌표값을 C언어의 2D Array에 맞게 변환해주어야 한다.

나는 기준점을 왼쪽 아래로 설정하였다. 이 부분을 기준점으로 한다는 것의 의미는, 기준점의 좌표값이 들어오면 색칠이 된다고 가정하였다. 첫번째로 입력되는 값, 즉 start_x, start_y의 값은 우리의 기준에 맞게 입력이 된다. 하지만, finish_x, finish_y의 값은 기준점의 마주보는 대각선에 위치하게 된다. 그래서 그 값을 finish_x--, finish_y-- 값으로 변환해주었다. 

그렇다면,  CheckRangeOver 함수도 영역체크 범위가 바뀐다. 기준점을 왼쪽 아래로 잡았으니, 아래가 아닌, 그 위여서는 안된다. 마찬가지로 오른쪽이여서도 안된다. 그래서 paper[i][j]가 입력될 수 있는 범위는 저 형광펜의 안쪽 부분이라고 할 수있다.

이 문제의 핵심은 DFS를 어떻게 구현하나라기 보다, scanf를 어떻게 받고, 영역범위를 어떻게 설정하느냐가 주된 문제인것 같다.

2. 음식물 피하기(boj.kr/1743)

#include <stdio.h>
 
#define MAX_SIZE 101
 
int N, M, K;
int edge[MAX_SIZE][MAX_SIZE];
int cnt, a;
int sizeArr[10000];//10000개정도까지 나올수 있음. sizeArr을 그냥 막 설정하지 말고, 몇개나올지 예상해보자.
int row[4] = { -1,0,1,0 };
int col[4] = { 0,-1,0,1 };
 
int CheckRangeOver(int i, int j) {
 
    return ((i > 0 && i <= N) && (j > 0 && j <= M));
    //좀 더 직관적일 수 있다.
}
 
int DFS(int i, int j) {
 
    edge[i][j] = 0;
 
    for (int a = 0; a < 4; ++a) {
 
        int y_row = i + row[a];
        int x_col = j + col[a];
 
        if (CheckRangeOver(y_row, x_col) && edge[y_row][x_col]) {
            /*CheckRangeOver(y_row,x_col)&&edge[y_row][x_col]==1,2랑 의미가 많이 다름,*/
            cnt++;
            DFS(y_row, x_col);
        }
    }
    return cnt;
}
 
int main(void) {
    int k = 0;
 
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 0; i < K; ++i) {
        int sero, garo;
        scanf("%d %d", &sero, &garo);
        edge[sero][garo] = 1;//방향그래프의 개념이 아니라서 edge[garo][sero]=1을 추가할 이유가 없음.
        //단순히 위치 설정을 의미함.
    }
 
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (edge[i][j] == 1) {
                cnt = 1;
                sizeArr[a++] = DFS(i, j);
            }
        }
    }
 
    k = sizeArr[0];
 
    for (int i = 0; i < a; ++i) {
        if (k < sizeArr[i]) {
            k = sizeArr[i];
        }
    }
 
    printf("%d\n", k);
    
    return 0;
}

사실 이 문제는 그닥 어렵지 않다고 생각했는데 너무 생각하지(?)않고 문제를 푼 것 같아서 반성차원으로 글을 쓴다..  sizeArr에서 배열의 크기 설정을 잘못해서 틀렸다. 배열의 크기를 설정할때마다, 왜 그렇게 설정했고, 어느정도의 크기가 필요한지 꼼꼼히 생각해서 정의하도록 하자..