2023.01.17 유기농 배추 백준

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

1012번: 유기농 배추

 

import sys
input = sys.stdin.readline
def main():
    def dfs(i,j):
        nonlocal graph
        discovered = [[i,j]]
        while discovered:
            pos = discovered.pop()
            graph[pos[0]][pos[1]] = 0
            next_pos = [[pos[0]+1,pos[1]],[pos[0]-1,pos[1]],[pos[0],pos[1]+1],[pos[0],pos[1]-1]]
            for np in next_pos:
                if 0<= np[0] < N and 0<= np[1] < M and graph[np[0]][np[1]] == 1:
                    discovered.append(np)
        return

    test_case = int(input().strip())
    for i in range(test_case):
        counters = 0
        M,N,K = map(int,input().split())
        graph = [[0] * M for _ in range(N)]
        pos = [list(map(int, input().split())) for _ in range(K)]
        for i in pos:   
            graph[i[1]][i[0]] = 1
        for i in range(N):
            for j in range(M):
                if graph[i][j] == 0:
                    continue
                dfs(i,j)
                counters += 1
        print(counters)
    return

main()

2차원 리스트를 돌면서 인접해있는 집단이 몇개있지 구하는 쉬운 그래프 문제였다. 백준은 재귀함수의 깊이 제한이 있어서 dfs를 재귀로 구현했다가 다시 while 문으로 바꿔주었다.