[파이썬/python] 백준 1012번 - 유기농 배추

import sys
T = int(sys.stdin.readline())
cnt = 0
ans = []


# dfs
def dfs(y, x):
    arr[y][x] = 0
    if y + 1 < N:
        if arr[y+1][x] == 1:
            dfs(y+1, x)
    if y - 1 >= 0:
        if arr[y-1][x] == 1:
            dfs(y-1, x)
    if x + 1 < M:
        if arr[y][x+1] == 1:
            dfs(y, x+1)
    if x - 1 >= 0:
        if arr[y][x-1] == 1:
            dfs(y, x-1)




for i in range(T):
    N, M, K = map(int, sys.stdin.readline().split())

    arr = [[0 for j in range(M)] for i in range(N)]

    for j in range(K):
        X, Y = map(int, sys.stdin.readline().split())
        arr[X][Y] = 1

    for n in range(N):
        for m in range(M):
            if arr[n][m] == 1:
                cnt += 1
                dfs(n, m)

    ans.append(cnt)
    cnt = 0
for i in ans:
    print(i)

그래프 이론 문제입니다.

2학기 자료구조 수업을 듣는 중이라 문제가 풀리네요.

왜 dfs를 썼냐.. 사실 bfs 써도 됩니다.

그냥 (제생각엔) dfs가 구현이 더 쉬워요.

 

구현방법:

N*M 크기의 2차원 배열을 선언하고 0으로 초기화합니다.

입력에 맞게 배추가 있는 곳을 1으로 바꿉니다.

모든 인덱스에 방문하며 dfs로 탐색하며 1인 곳이 있을 때마다 카운트 하며 방문한 곳을 0으로 바꿔줍니다.

(근거 : N, M 은 50보다 작으므로 최대 크기는 2500입니다. 시간 초과 문제는 없을겁니다.)

 

TIP:

arr = [[0 for j in range(M)] for i in range(N)]

N*M크기의 배열을 선언하며 0으로 초기화하는 코드입니다.

정말.. 간편하네요.

오늘도 하나 배워갑니다.