[백준 1012] 유기농 배추 with Python

🔗 문제 링크

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

1012번: 유기농 배추

✏️ 풀이

import sys
from collections import deque

def bfs(start):
    visited = [start]
    queue = deque([start])
    while queue:
        cur_node = queue.pop()
        for i in graph[cur_node]:
            if i not in visited:
                visited.append(i)
                queue.append(i)

    return visited

T = int(sys.stdin.readline())
for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split())
    graph = {tuple(map(int, sys.stdin.readline().split())):[] for _ in range(K)}
    for x, y in graph.keys():
        for adj_x, adj_y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if (x+adj_x, y+adj_y) in graph.keys():
                graph[(x+adj_x, y+adj_y)].append((x, y))

    count = 0
    coord = [x for x in graph]
    while coord:
        visited = bfs(coord[0])
        for i in visited:
            coord.remove(i)
        count += 1
    print(count)

graph라는 딕셔너리를 만들어서 배추가 있는 좌표의 튜플 형태를 키로, 인접한 좌표의 튜플이 담긴 리스트를 값으로 갖도록 했다. 그리고 상하좌우로 인접한 칸 중에 배추가 있는 칸만을 골라서 인접한 노드들을 리스트에 추가하였다.

 

배추가 있는 좌표들만을 순회하면서 BFS를 하고 방문한 좌표들은 제거하기를 반복하면서 그 횟수를 세어 출력하였다.

 

 

🗃️ 다른 언어로 된 풀이

[백준 1012 - Node.js] 유기농 배추