[S2] 백준 1012 - 유기농 배추 (Python3)

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

1012번: 유기농 배추

---

해결방법

배추가 상하좌우로 모여 있는 곳 하나당 필요한 배추흰지렁이 수가 된다. 그러므로 이렇게 모여있는 군집이 몇 개 인지만 파악하여 출력하는 것이 목표이다.

파악하는 방법은 DFS, BFS 등이 있는데 이 글에선 BFS를 다루고 있다.

grid를 일일이 탐색하다가 배추가 있는 자리라고 표시해둔 곳을 마주치게 되면, BFS를 통해서 상하좌우에 위치한 배추들을 0으로 바꾸어준다. 0으로 바꾸는 이유는 '탐색을 완료한 자리'라고 표시하기 위함이다.

그렇게 grid에서의 탐색을 모두 마치면 답을 출력한다.

---

코드

from collections import deque

# 북 동 남 서
dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1]

T = int(input())
for _ in range(T):
    M, N, k = map(int, input().split())
    grid = [[0 for i in range(M)] for j in range(N)]
    for __ in range(k):
        # 배추의 좌표
        x, y = map(int, input().split())
        grid[y][x] = 1

    # 배추 군집의 수 = 필요한 배추흰지렁이의 수
    cnt = 0

    # grid의 모든 좌표를 일일이 살펴보면서 1이라고 표시되어 있는 곳에서 bfs를 돌린다.
    # bfs를 돌림으로써 배추 군집이 몇 개 있는지 탐색한다.
    # 탐색할 땐 cnt를 하나 증가시켜준다.
    # 탐색하면서 다른 배추 좌표들을 모두 0으로 바꾸어준다.
    for i in range(N):
        for j in range(M):
            elem = grid[i][j]

            if elem == 1:
                # 좌표에 있는 값이 1이므로 탐색한다.
                q = deque()
                q.append((i, j))
                cnt += 1
                while q:
                    y, x = q.popleft()
                    for dire in range(4):
                        ny, nx = y+dy[dire], x+dx[dire]
                        # 범위 안에 있는지 확인한다.
                        if 0<=ny and ny<N and 0<=nx and nx<M:
                            # 해당 좌표의 값이 1인지 확인해본다.
                            if grid[ny][nx] == 1:
                                # 1이라면 0으로 바꾸고 그 좌표의 상하좌우를 살피기 위해 queue 안에 좌표를 넣는다.
                                grid[ny][nx] = 0
                                q.append((ny, nx))
    print(cnt)

코드 설명

위 주석들로 대신하겠다.

---

11분 전 - BFS 풀이;   4달 전 - DFS 풀이