백준 알고리즘 1012: 유기농 배추(Python)

www.acmicpc.net/problem/1012

1012번: 유기농 배추

---

문제 해결을 위한 과정

이 문제의 경우 전형적인 BFS알고리즘을 이용하면 쉽게 해결할 수 있는 문제였습니다. 먼저 문제의 입력 조건을 입력받은 후 n행 m열 그래프를 생성한 후 이중 for문을 이용하여 그래프의 값들을 조회해나가면서 BFS함수가 호출될 때마다 count를 하나 증가시켜주고 조회가 끝나면 count값을 출력해주면 됩니다. visited그래프를 생성하기보다는 탐색하면 graph[x][y]값을 2로 바꿔주면 보다 쉽게 해결할 수 있습니다. 

---

소스코드

from collections import deque
 
tc = int(input())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
for i in range(tc):
    n, m, k = map(int, input().split())
    graph = [[0] * m for _ in range(n)]
    for _ in range(k):
        a, b = map(int, input().split())
        graph[a][b] = 1
    
    def bfs(graph, xPos, yPos):
        q = deque()
        q.append((xPos, yPos))
        graph[xPos][yPos] = 2
        while q:
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m:
                    if graph[nx][ny] == 1:
                        q.append((nx, ny))
                        graph[nx][ny] = 2
    count = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                bfs(graph, i, j)
                count += 1
    print(count)