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

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

1012번: 유기농 배추

접근 방식

- 함수 선정 (bfs, dfs)

- 그래프 특정 좌표 방문 처리 방식 고민

- 적절한 count 시점 고민

 

코드 풀이

from collections import deque
t = int(input()) # 몇 번의 테스트케이스인지

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

def bfs(graph, x, y): # bfs 함수 구현
    q = deque()
    q.append([x, y])
    graph[x][y] = 0 # 방문 처리; 처리 방식: 표기된 1을 0으로 바꾸기
    
    while q: # q가 비었다 = 탐색 가능한 연속 영역 모두 탐색하였다.
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<m and 0<=ny<n and graph[nx][ny] == 1: # 배추밭 범위를 벗어나지 않고 미방문한 좌표인 경우
                q.append([nx, ny])
                graph[nx][ny] = 0


for _ in range(t):  
    m, n, k = map(int, input().split())
    graph = [[0]*(n) for _ in range(m)] # 빈 배추밭
    for _ in range(k):
        a, b = map(int, input().split())
        graph[a][b] = 1 # 배추 위치 표기
        
    cnt = 0
    for j in range(m):
        for k in range(n):
            if graph[j][k] == 1:
                bfs(graph, j, k)
                cnt+=1 # bfs 함수 들어갈때마다 count; 하나의 연속 영역이 끝날 때마다
    print(cnt)

이 문제는 연속된 배추 영역의 개수를 구하면 되는 문제이며, 테스트케이스가 여러 개일 수 있다는 점에서 약간의 코딩상 귀찮음(?)이 가미된 문제입니다. 연속된 영역의 개수를 셀 때는 사실 bfs 방식이던 dfs 방식이던 모두 활용해 각각의 영역을 체크할 수 있지만, 상하좌우로 좌표를 이동시키며 탐색할 수 있는 bfs 방식이 조금 더 범용적으로 활용되는 것 같습니다.

위의 문제는 방문 처리 방식은 따로 visited 리스트를 활용하지 않고, 그래프상에서 1을 0으로 바꾸어주는 방식을 활용했습니다. 그래프의 변형이 탐색 결과에 영향을 주지 않기 때문입니다. 그리고 연속된 영역의 개수는, 그래프의 좌표를 이중 for문으로 일일히 체크해주며 bfs 함수에 한번 들어갈때마다 count해주는 방식으로 코드를 작성했습니다. 한번 bfs 그래프에 들어가면, input 좌표와 연속된 배추 영역은 모두 방문처리가 완료되기 때문입니다. count 위치와 graph의 x, y 이중 리스트 문법, 방문처리 시점에서 실수가 발생할 수 있는 문제입니다.