[Python]Baekjoon 1012번: 유기농 배추(BFS)

1. 문제

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

1012번: 유기농 배추

1로 구성된 영역이 총 몇개가 있는지 찾는 문제이다.

상, 하, 좌, 우 중 하나가 연결되어 있다면 인접한 것이고 같은 영역으로 카운트 된다.

하지만 4방향 중 어느 하나에도 연결되어 있지 않다면 인접하지 않은 것이고 다른 영역으로 카운트 해줘야 한다.

2. 풀이

BFS를 이용하여 풀이할 것이므로 deque를 활용할 것이다.

그래프를 탐색하기 위해 x, y좌표를 변화시킬 때 사용할 리스트가 필요하다.

(-1, 0), (1, 0), (0, -1), (0, 1) 방향으로 탐색하기 위해 dx, dy를 적절하게 세팅한다.

BFS를 수행할 함수를 작성하는데, 이 함수에서는 방문한 좌표를 0으로 바꾸고(방문처리)

상, 하, 좌, 우로 이동하며 만약 방문하지 않은 1이 있다면 큐에 해당 좌표를 추가하고 방문처리를 한다.

BFS 함수가 종료되었다는 것은 인접한 배추를 모두 방문했다는 뜻이고,

BFS가 다시 실행된다면 인접하지 않은 배추를 만났다는 뜻이므로 cnt + 1을 해준다.

3. 코드

import sys

from collections import deque

input = sys.stdin.readline

T = int(input())

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

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

def BFS(x,y):

queue = deque()

queue.append((x,y))

while queue:

x, y = queue.popleft()

for i in range(4):

nx = x + dx[i]

ny = y + dy[i]

if nx < 0 or ny < 0 or nx >= N or ny >= M:

continue

if matrix[nx][ny] == 1:

queue.append((nx, ny))

matrix[nx][ny] = 0

return

for _ in range(T):

M, N, K = map(int, input().split())

matrix = [[0]*M for _ in range(N)]

for i in range(K):

x, y = map(int, input().split())

matrix[y][x] = 1

cnt = 0

for i in range(N):

for j in range(M):

if matrix[i][j] == 1:

BFS(i, j)

cnt += 1

print(cnt)

4. 느낀점

본격적인 그래프 탐색 문제였다.

처음에는 이해가 잘 되지 않았지만, 구글링을 통해 조금씩 코드를 이해할 수 있었다.

여러 문제를 풀어보면서 그래프 탐색 형태에 좀 더 익숙해 져야 할 것 같다.

오늘 하루도 쌓였다.