BOJ 1012 유기농 배추 python

마찬가지로 기본적인 그래프 탐색 문제이다. 지금까지 풀었던 것들과 한 가지 다른 점은 그래프의 형태이다.

기

그래프를 지금과 다른 형식으로 작성한다. 기본적으로 m * n 행렬을 만든 후, 배추의 좌표들을 입력하여 그래프를 완성한다.

마찬가지로 bfs를 사용하여, 이번에는 그래프가 총 몇 개 나오는 지 카운트해야 한다는 사실을 파악한다.

승

이런 형식의 문제를 풀 때, 약간의 정해진 포맷이 있음을 검색을 통해 알게 되었다. 이 문제를 풀어봄으로써 해당 포맷에 익숙해지는 것을 목표로 하였다.

1. 그래프를 탐색하면서, 배추가 들어있는, 즉 내용이 1인 좌표를 찾으면, 그 좌표에서부터 탐색을 시작한다.

2. 해당 좌표의 상하좌우를 탐색한다. 이 때 앞서 언급한 포맷을 이용한다.

3. 큐를 이용해 bfs를 진행한다.

전

구현은 다음과 같이 진행되었다.

1. 1이 들어있는 좌표를 찾으면 해당 좌표를 큐에 넣은 후 방문 처리를 한다.

2. dx, dy 배열을 이용하여 상하좌우를 탐색한다. 이 때 1이 있으면 그 좌표들을 방문처리하고 큐에 넣는다.

3. 한 그래프에 대해 bfs가 완료될 때마다 cnt를 1 증가시킨다 -> 총 그래프의 개수를 찾을 수 있다!

결

bfs의 과정에서 까다로운 처리가 필요없는 직관적인 문제였다.

또한 행렬 형태로 주어지는 그래프에서의 전통적인 탐색 방법을 연습해 볼 수 있는 좋은 기회였다.

---

코드

from collections import deque

T = int(input())

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

def bfs(graph, x, y):
    q = deque([(x,y)])
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= len(graph) or ny >= len(graph[0]):
                continue
            elif graph[nx][ny] == 1:
                q.append((nx, ny))
                graph[nx][ny] = 0
    return graph

for t in range(T):
    w,h,B = map(int, input().split())
    graph = [[0]*w for _ in range(h)]
    for b in range(B):
        x, y = map(int, input().split())
        graph[y][x] = 1
    cnt = 0
    for x in range(len(graph)):
        for y in range(len(graph[0])):
            if graph[x][y] == 1:
                cnt += 1
                graph = bfs(graph, x, y)
    print(cnt)