DFS 문제 분석-2(적록색약, 연결 요소)

Bool을 이용해서 방문체크 하기

1. 적록색약 문제 분석(boj.kr/10026)

#include <stdio.h>
//#include <string.h> memset을 이용할 수 있다.
#define MAX_SIZE 101
#define TRUE 1
#define FALSE 0
 
char painting[MAX_SIZE][MAX_SIZE];
int bool_visit[MAX_SIZE][MAX_SIZE];
int N;
int row[4] = { -1,0,1,0 };
int col[4] = { 0,-1,0,1 };
 
/*
checkRangeOver
함수명 그대로, 탐색범위를 초과하는지 체크한다.
*/
int checkRangeOver(int i, int j) {
 
    return !(i<0 || i>N || j<0 || j>N) ? TRUE : FALSE;
}
 
/*
bool_visitInit
bool초기화하기. memset으로 할 수있다.(string.h)
*/
void bool_visitInit() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            bool_visit[i][j] = 0;
        }
    }
}
 
void painting_DFS(int i, int j, char color) {
    bool_visit[i][j] = 1;//방문했다면, 1로 체크.
 
    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)) continue;
 
        if (!bool_visit[row_y][col_x] && color == painting[row_y][col_x])
            painting_DFS(row_y, col_x, color);
    
    }
}
 
/*
painting_OF_ColorBlindness
적록색약에게 보이는 그림으로 바꾼다.
*/
void painting_OF_ColorBlindness(void) {
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (painting[i][j] == 'G') painting[i][j] = 'R';
        }
    }
 
}
 
int main(void) {
    int not_bli = 0, bli = 0;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf(" %c", &painting[i][j]);
        }
    }
    
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (!bool_visit[i][j]) {
                painting_DFS(i, j, painting[i][j]);
                not_bli++;
            }
        }
    }
 
    bool_visitInit();//memset(bool_visit,0,MAX_SIZE);
    
    painting_OF_ColorBlindness();
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (!bool_visit[i][j]) {
                painting_DFS(i, j, painting[i][j]);
                bli++;
            }
        }
    }
 
    printf("%d %d\n", not_bli, bli);
    
    return 0;
}

방문체크를 bool을 이용해서 할 수 있다. 그 전에는 입력된 값을 1 또는 2로 변형해서 했다. 하지만, 이 문제에서는 1 또는 2의 값을 주는 형식으로 바꾸어버리면, 입력값이 달라지기 때문에, painting_Of_ColorBlindness의 결과를 제대로 수행할 수 없다.(입력값은 변형하지 않는게 좋다) 그래서, bool을 이용하기로 했다. (i, j)의 값은 방문한 노드를 가리킨다. painting[i][j]를 방문 했으면 bool_visit[i][j]=1을 넣어준다. 이와같이, 노드의 방문여부를 체크하는 bool을 만들어서, 초기값을 변형하지 않고 탐색할 수 있다.

<탐색 전 bool_visit>

<(i, j)==(0, 0)부터 탐색 한 후>

 

bool 행렬을 이용해서, 탐색 여부를 체크할 수 있다.

2. 연결 요소의 개수(boj.kr/11724)

#include <stdio.h>
 
#define MAX_SIZE 1005
 
int N, M;
int edge[MAX_SIZE][MAX_SIZE];
int bool_visit[MAX_SIZE];
 
void DFS(int cur) {
    bool_visit[cur] = 1;
 
    for (int i = 1; i <= N; ++i) {
        if (!bool_visit[i] && edge[cur][i])
            DFS(i);
    }
}
 
int main(void) {
    int DFS_cnt = 0;
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        edge[b][a]=edge[a][b] = 1;
        //무방향 그래프라서...
    }
 
    for (int i = 1; i <= N; ++i) {
        if (!bool_visit[i]) {
            DFS(i);
            DFS_cnt++;
        }
    }
 
    printf("%d\n", DFS_cnt);
 
    return 0;
}

각 노드들이 어떻게 연결 상태를 배열 edge로 확인 할 수 있다.

입력 상태는 다음과 같다.

처음 bool_visit의 초기화 상태이다. 0은 방문하지 않았음을 뜻한다. 

어떤 노드도 방문하지 않은 상태.

무방향 그래프, 그래서 edge[b][a]=edge[a][b]=1;

이제 DFS함수를 보자.

void DFS(int cur) {
    bool_visit[cur] = 1;
 
    for (int i = 1; i <= N; ++i) {
        if (!bool_visit[i] && edge[cur][i])
            DFS(i);
    }
}
 

처음 cur=1의 값이 들어온다. 그러면 이제 1은 방문한 상태이다.즉  !bool_visit[1]=0이라서 i의 값은 2가 된다. edge 행렬의 상태를 보니, 1,2가 연결되어 있다. 그러므로, 1과 2는 서로 연결상태에 있다. 그러면 DFS(2)가 실행된다. 그러면 새롭게 생성된 함수레코드에서 bool_visit[2]=1로 되어 방문 상태가 된다. i가 증가하면서 2,3,4,와는 연결이 안되어있다. 하지만 (2,5)가 1이다. 즉, 연결되어 있는 상태이다. 그래서 bool_visit[5]=1이 된다. 하지만 그 이후로, 1,2,5,는 서로서로를 제외하고, 어떠한 노드와 연결되어 있지 않다. 그래서 DFS(1)은 이렇게 끝난다.

DFS(1)의 결과