[Python] 백준, 1012(DFS/BFS)

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

1012번: 유기농 배추

DFS알고리즘으로 접근했을 때 계속 인덱스 에러가 나서 고생했다. 

 

# PYTHON CODE (1) - DFS

import sys

sys.setrecursionlimit(2500)

t = int(sys.stdin.readline())


def dfs(a, b):
    if a < 0 or a >= n or b < 0 or b >= m:
        return False

    if tree[a][b] == 1:
        tree[a][b] = 0
        for xy in range(4):
            nx = b + dx[xy]
            ny = a + dy[xy]
            dfs(ny, nx)
        return True
    return False


for i in range(t):
    answer = 0
    m, n, k = map(int, sys.stdin.readline().split())
    tree = [[0] * m for _ in range(n)]

    for j in range(k):
        a, b = map(int, sys.stdin.readline().split())
        tree[b][a] = 1

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for my in range(n):
        for mx in range(m):
            if dfs(my, mx):
                answer += 1

    print(answer)

sys모듈의 setrecursionlimit(n)은 python에 기본적으로 설정되어 있던 재귀 함수의 참조값을 늘려주는 모듈이다. RecursionError를 방지하기 위해 사용한다고 한다. (정학히 어떤 값을 넣어야 탈출하는지는 잘 모르겠다....)

 

dfs 함수를 작성할 때, 조금 더 신중히 생각을 해야겠다. dfs 함수에서 계속 인덱스 오류가 발생했고, 이전 풀이랑 비교해서 풀어내긴 했지만 아직 매끄럽게 작성할 실력은 아닌듯하다.

 

 

# PYTHON CODE (2) - BFS

import sys

t = int(sys.stdin.readline())


def bfs(a, b):
    queue = [[a, b]]
    cnt = 1

    while queue:
        x, y = queue[0]
        del queue[0]

        for xy in range(4):
            nx = x + dx[xy]
            ny = y + dy[xy]

            if nx >= m or nx < 0 or ny < 0 or ny >= n:
                continue

            if tree[nx][ny] == 1:
                cnt += 1
                tree[nx][ny] = 0
                queue.append([nx, ny])
    return cnt


for i in range(t):
    answer = []
    m, n, k = map(int, sys.stdin.readline().split())
    tree = [[0] * n for _ in range(m)]

    for j in range(k):
        a, b = map(int, sys.stdin.readline().split())
        tree[a][b] = 1

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for mx in range(m):
        for my in range(n):
            if tree[mx][my] == 1:
                tree[mx][my] = 0
                answer.append(bfs(mx, my))

    print(len(answer))

비교적 간단히 풀었다.