백준 1012번 유기농 배추

 

 

 

 

 

 

입출력 조건은 다음과 같다.

 

 

 

 

 

 

 

 

• 각 테스트 케이스에 대해 M x N 크기의 2차원 리스트 field를 생성했다.
• 입력받은 배추의 위치를 field에 표시하여 1로 설정한다.
• field를 순회하면서 아직 방문하지 않은 배추(1)를 발견하면
  -해당 위치에서 DFS를 시작합니다.
  -DFS는 연결된 모든 배추를 방문했다고 0으로 변경한다.
  -DFS가 종료되면 하나의 연결된 배추 그룹을 모두 처리한 것이므로 count를 +1한다.
• 모든 배추를 처리할 때까지 반복문으로 처리한다.

 

 

 

import sys
sys.setrecursionlimit(10000)

def dfs(x, y):
    # 주어진 범위를 벗어나는 경우 즉시 종료
    if x < 0 or x >= M or y < 0 or y >= N:
        return
    
    # 현재 노드를 아직 방문하지 않았다면
    if field[y][x] == 1:
        # 해당 노드 방문 처리
        field[y][x] = 0
        
        # 상하좌우 위치 모두 재귀적으로 호출
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)

T = int(input())

for _ in range(T):
    M, N, K = map(int, input().split())
    field = [[0] * M for _ in range(N)]
    
    # 배추 위치 입력
    for _ in range(K):
        X, Y = map(int, input().split())
        field[Y][X] = 1
    
    count = 0
    for y in range(N):
        for x in range(M):
            if field[y][x] == 1:
                dfs(x, y)
                count += 1
    
    print(count)