[Baekjoon, Python] 1012번 : 유기농 배추

도입

백준 단계별 풀기 DFS와 BFS 네 번째 문제이다.

---

백준 1012번 문제, 입력, 출력

---

백준 1012번 입출력 예제 1, 2

---

DFS와 BFS

DFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법.

한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행.

- Stack 또는 Recursive함수로 구현.

- 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

BFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색.

- Queue로 구현

- 시간 복잡도 :  인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

---

풀이

1. 이전의 단지번호붙이기 문제와 같이 좌표를 활용하는 문제이다. 2차원 배열(fied)의 인덱스 값을 좌표로 사용한다. 또한, dx, dy로 상, 하, 좌, 우를 확인하고자 한다.

 

2. dfs로 인접한 배추들(노드들)을 하나의 배추흰지렁이(var_cnt)로 계산한다. dfs를 호출한다는 것은, 인접한 배추로 가는 것을 의미하는데, 그렇다면 배추흰지렁이(var_cnt)를 어디서 카운팅하는지를 고민해 봐야한다. 어렵지 않다. field[i][j] = 1일때 bfs를 콜을 하고 dfs를 끝내고 서브루틴이 전부 끝난 부분에서 var_cnt += 1을 해준다. 

 

3. dfs 함수 시작부분에서, field[x][y] 에 0의 값을 넣는다. 방문한 곳은 방문했다고 0값을 넣어줘서 재방문을 방지하기 위함이다. 

 

4. 문제를 풀다가 RecursionError를 만나서 확인해보았다. BOJ 사이트에서는 가장 많이 발생하는 이유로 'Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때'라고 설명하고 있다. 1000으로 제한하고 있는데, sys.setrecursionlimit(10000)으로 제한의 정도를 10배 더 주었더니, 해결이 되었다. 파이썬으로 재귀함수를 쓸 때, 특히 DFS, BFS에서는 필수적인 코드라고 설명을 하고 있다.

5. 2차원 배열의 선언에서 2중 for문, 1 연산자와 1 for문, 2 연산자 방법이 있다. 틀렸습니다가 나오길래...로직에서 문제를 도저히 찾지 못했다. field의 선언 문제인가 싶어서 처음에 진행했던 2연산자 방법( [[0]*var_x]*var_y )에서 1연산자 1 for문( [[0]*var_x for _ in range(var_y)] )으로 하니까 되었다....

---

코드

import sys
from sys import stdin
sys.setrecursionlimit(10000)

dx=[-1,0,1,0] # 좌  우 
dy=[0,1,0,-1] #   상  하

def dfs(x,y):
    field[x][y] = 0 # 방문한 배추는 0
    for i in range(4):
        nx = x + dx[i] #i=0 좌 , i=1 상, i=2 우 , i=3 하
        ny = y + dy[i]
        
        if (0 <= nx < var_y) and (0 <= ny < var_x):
            if field[nx][ny] == 1:
                dfs(nx, ny)

var_test_case = int(stdin.readline())
for _ in range(var_test_case):
    # 가로길이, 세로길이, 배추 개수
    var_x, var_y, var_cabbage = map(int, stdin.readline().split())
    # field = [[0]*var_x]*var_y # 2중 연산자로 2차원 배열 초기화 (틀렸습니다)
    field = [[0]*var_x for _ in range(var_y)]
    var_cnt = 0

    # 배추 심기
    for _ in range(var_cabbage):
        ty,tx = map(int, stdin.readline().split())
        field[tx][ty] = 1
    # 벌레 수 정하기
    for i in range(var_y):
        for j in range(var_x):
            if field[i][j] > 0 :
                dfs(i,j)
                var_cnt += 1
    print(var_cnt)

---

마무리

*^^*