[BOJ] 1012. 유기농 배추,py(BFS, DFS, Flood Fill)

#. Problem

https://www.acmicpc.net/problem/1012

* The copyright in this matter is in BOj

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

섬의 개수(?)를 구하는 문제랑 같다.

DFS, BFS 모두 구현 가능하다.

<BFS>

1. 초기값이 0으로 채워진 이차원 배열을 생성한 후 배추가 심어져있는 위치를 1로 수정

2. 지금부터 BFS 작동! 편의를 위해 (1, 1)부터 (n, n)까지 돌면서

- 해당 좌표 값이 1일 경우, queue가 빌 때까지 반복, 상하좌우를 탐색

- 주위에 1이 있다면 queue에 넣어주고 해당 좌표는 0으로 수정

- 해당 queue가 비워지고 해당 반복문이 끝나면 cnt++

<DFS>

1. 초기값이 0으로 채워진 이차원 배열을 생성한 후 배추가 심어져있는 위치를 1로 수정

2. 지금부터 DFS 작동! 편의를 위해 (1, 1)부터 (n, n)까지 돌면서

- 해당 좌표 값이 1일 경우, DFS()를 호출하고 cnt++

- DFS에서는 해당 좌표를 방문하였으므로 0으로 수정하고, 상하좌우를 탐색

- 주변에 배추가 있을 경우 다시 DFS()를 호출

#. C++ Code

python이랑 아직 친해지지 않아서..  C++로 먼저 코딩을 해보았다.

DFS()로 구현하였다.

#include <cstdio>
 
const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };
 
int map[52][52];
 
void DFS(int x, int y)
{
    int p, xx, yy;
 
    map[x][y] = 0;
    for (p = 0; p < 4; p++)
    {
        xx = x + dx[p];
        yy = y + dy[p];
 
        if (map[xx][yy])
            DFS(xx, yy);
    }
}
 
void process()
{
    int M, N, K, i, j, a, b, cnt = 0;
    scanf("%d %d %d", &M, &N, &K);
 
    while(K--)
    {
        scanf("%d %d", &a, &b);
        map[++a][++b] = 1;
    }
 
    for (i = 1; i <= M; i++)
    {
        for (j = 1; j <= N; j++)
        {
            if (map[i][j])
            {
                DFS(i, j);
                cnt++;
            }
        }
    }
 
    printf("%d\n", cnt);
}
 
int main(void)
{
    int tc;
    //freopen("input.txt", "rt", stdin);
    scanf("%d", &tc);
    while(tc--)
        process();
 
    return 0;
}

line 38) 해당 좌표가 1일 경우, DFS() 함수 호출, cnt++

line 12) 해당 좌표를 방문하였으므로 0으로 수정

line 13~20) 상하좌우에 또 다른 배추가 있는지 탐색

line 18) 주변에 배추가 또 있을 경우 DFS() 호출

#. Python Code

import sys
sys.setrecursionlimit(10000)
 
dx, dy = [0, 1, -1, 0], [1, 0, 0, -1]
grd, ck = [], []
T = int(input())
 
def dfs(x, y):
    global grd, ck
    if ck[x][y] == 1:
        return
    ck[x][y] = 1
    for i in range(4):
        xx, yy = x + dx[i], y + dy[i]
        if grd[xx][yy] == 1 and ck[xx][yy] == 0:
            dfs(xx, yy)
 
def process():
    global grd, ck;
    M, N, K = map(int, input().split())
    grd = [[0 for i in range(M + 2)] for j in range(N + 2)]
    ck = [[0 for i in range(M + 2)] for j in range(N + 2)]
    for _ in range(K):
        X, Y = map(int, input().split())
        grd[Y+1][X+1] = 1
    rst = 0
    for i in range(1, N+1):
        for j in range(1, M+1):
            if grd[i][j] == 1 and ck[i][j] == 0:
                dfs(i, j)
                rst += 1
    print(rst)
 
for _ in range(T):
    process()

line 1~2) 재귀함수 깊이 제한 함수 선언

line 19) 파이썬에서는 전역변수 사용을 위해 global 을 선언해주어야 한다.

line 25) 가로, 세로로 순서로 입력받았으므로, Y, X 순서로 입력해준다.

line 27~31) 모든 좌표를 방문하면서 배추가 있고, 방문하지 않은 좌표가 발견되었다면

line 30) dfs() 함수를 호출

line 31) count++

line 8~16) dfs() 함수

line 9) 마찬가지로 전역변수 사용을 위해 global 선언

line 10~11) 이미 방문한 좌표라면 return

line 12) 방문 check

line 13~16) 주변 상하좌우를 탐색

line 14) 다음 좌표를 변수에 저장

line 15~16) 배추가 있고 방문하지 않은 좌표라면 dfs() 호출

* python에서 DFS사용 시 재귀함수 깊이 제한 함수를 선언해야 한다는 것을 알게 되었다.

sys.setrecursionlimit()

* python에서 전역변수 사용 시 global 선언