[백준] 1012번 유기농 배추 | 파이썬 Python 너비 우선 탐색(BFS)으로 구현

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

 

백준 1012번 유기농 배추 문제 - 너비 우선 탐색(breadth-first search)으로 풀었다.

 

 

문제

 

 

 

설명

 

문제가 길지만 간단히 말하면 섬의 개수를 구하는 문제이다.

1이 상,하,좌,우로 붙어있고 0으로 둘러 싸여있으면 하나의 섬이다.

 

코드는 그래프를 완전 탐색해서 1이 나오면 BFS를 실행한다.

BFS 내에서 섬 전체를 훑어가며 1에서 0으로 바꿔준다.

너비 우선 탐색에 대해 알고 있으면 쉽게 풀리는 문제이지만

혹시 이해가 안간다면 더 쉬운 백준 BFS 문제 2178번 미로 탐색을 추천한다.

 

[백준] 2178번 미로 탐색 / 파이썬 python 너비 우선 탐색(bfs) 구현

 

 

코드

 

from collections import deque
import sys
input = sys.stdin.readline

dx = [0,1,0,-1]			# 상, 하, 좌, 우 탐색용
dy = [1,0,-1,0]

def bfs(x, y):
    q = deque()
    q.append((x, y))
    graph[x][y] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= col or ny < 0 or ny >= row:
                continue
            if graph[nx][ny] != 0:		# 한번 밟은 땅은 1에서 0으로 변경
                graph[nx][ny] = 0
                q.append((nx, ny))

testcase = int(input())
for _ in range(testcase):
    row, col, k = map(int, input().split())
    graph = [[0]*row for _ in range(col)]

    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1

    cnt = 0
    for x in range(col):
        for y in range(row):
            if graph[x][y] != 0:
                cnt += 1
                bfs(x, y)
    print(cnt)