[백준] 1012번 유기농 배추(파이썬)

문제

1012번: 유기농 배추

DFS BFS 재귀방식으로 풀 수 있다.

 

주의

런타임 에러 (RecursionError)가 발생한다면

재귀함수 특성상 최대깊이가 깊어져서 발생하는 것이니 아래 코드를 꼭  넣어주자!

import sys
sys.setrecursionlimit = 10**6

코드

DFS

import sys
input = sys.stdin.readline
sys.setrecursionlimit = 10**6

def dfs(graph, visited, i, j):
    global Y, X
    for _ in range(4):
        I = i + dx[_]
        J = j + dy[_]

        if 0 <= I < X and 0 <= J < Y and graph[I][J] == 1 and visited[I][J] == False:
            visited[I][J] = True
            dfs(graph, visited, I, J)


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

n = int(input())

for _ in range(n):
    Y, X, K = map(int, input().split())

    graph = [[0] * Y for _ in range(X)]
    visited = [[False] * Y for _ in range(X)]

    for k in range(K):
        y, x = map(int, input().split())
        graph[x][y] = 1

    cnt = 0
    for i in range(X):
        for j in range(Y):
            if graph[i][j] == 1 and visited[i][j] == False:
                visited[i][j] = True
                dfs(graph, visited, i, j)
                cnt += 1
    
    print(cnt)

BFS

from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit = 10**6

def bfs(graph, visited, i, j):
    global Y, X
    q = deque([(i, j)])
    visited[i][j] = True

    while q:
        i, j = q.popleft()
    
        for _ in range(4):
            I = i + dx[_]
            J = j + dy[_]

            if 0 <= I < X and 0 <= J < Y and graph[I][J] == 1 and visited[I][J] == False:
                q.append((I, J))
                visited[I][J] = True

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

n = int(input())

for _ in range(n):
    Y, X, K = map(int, input().split())

    graph = [[0] * Y for _ in range(X)]
    visited = [[False] * Y for _ in range(X)]

    for k in range(K):
        y, x = map(int, input().split())
        graph[x][y] = 1

    cnt = 0
    for i in range(X):
        for j in range(Y):
            if graph[i][j] == 1 and visited[i][j] == False:
                bfs(graph, visited, i, j)
                cnt += 1
    
    print(cnt)

 

해설

함수를 이용해서 재귀하여 푸는 문제이다.

내 입력을 받는 graph와 방문 기록을 체크하는 visited를 만든다.

 

DFS는 방문하지 않고 벌레가 있는 곳(=1)에 들어가서 재귀를 하면서 한 벌레가 관리하는 곳을 체크한다.

더이상 체크할 곳이 없으면 cnt+=1를 하여 벌레 한마리를 센다.

 

BFS는 방문하지 않고 벌레가 있는 곳(=1)의 자리를 q에 넣는다.

q가 없을 때까지 while 문을 반복한다.

q에서 제일 앞에 있는 것을 체크하고 pop한다.

체크 된 부분에 들어거서 4반향 중 연결 된 부분을 모두 체크한다.

q가 없을 때까지 while 문을 반복한다