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

백준 1012번: 유기농 배추
Graph theory / DFS / BFS

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

1012번: 유기농 배추

1. 문제 설명

유기농 배추는 해충으로부터 보호하기 위해 배추흰지렁이가 총 몇 마리가 필요한지 구하는 문제이다.

전형적인 그래프 이론 문제로, 이를 해결하기 위해 DFS 혹은 BFS를 사용하여 해결한다.

 

배열이 주어지는 그래프 이론의 문제를 처음 접하면 문제를 읽고 이해하기가 난감한 경우가 발생한다.

특히 배추흰지렁이의 이동 루틴이 헷갈리는 경우를 많이 봤다.

지렁이가 특정 위치에서 상하좌우만 이동 가능한 것이 아니라, 상하좌우로 연결된 인접한 배추면 모두 이동할 수 있다.

 

아래와 같은 배열이 주어진다고 가정하자.

1	1	1
1	1	1
1	1	1

배열의 임의의 위치로 지렁이를 위치시키면

상하좌우로 인접한 배추로 이동할 수 있으므로 1마리면 충분하다.

 

문제에서 주어진 배열은 아래와 같다.

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

상하좌우로 인접한 배열은 지렁이가 이동할 수 있으므로 한 마리로 정리할 수 있다.

따라서 총 다섯 마리가 필요할 것이고, 그것이 문제에서 구하고자 하는 정답일 것이다.

---

2. 문제 접근

기본적으로 모든 배추밭의 인덱스에 한 번씩 접근해야 하므로 배열의 처음부터 끝까지 반드시 탐색해야 한다.

따라서 Nested loop를 이용하여 배열의 모든 행과 열을 방문하도록 한다.

이때 방문한 곳은 중복 방문을 하지 않도록 반드시 방문 표시를 해주도록 하자.

 

만약 해당 배열의 값이 1이라면(=배추) 그 부분에서 BFS로 인접한 배추에 방문하고, 방문한 곳에 모두 방문 표시를 한다.

보통 문제라면 방문 여부를 체크할 배열을 하나 만들어서 확인한다.

그러나, 이 문제에서는 방문한 경우 1을 0으로 바꿔주면 쉽게 해결된다. (배추 밭을 맨땅으로 업데이트)

그리고 필요한 지렁이 개수를 하나 증가시킨다.

 

이 과정을 Nested loop가 끝날 때까지 반복하면

우리가 구하고자 하는 필요한 최소 배추흰지렁이 마리 수를 구할 수 있다.

 

#  DFS로도 구할 수 있지만, RecursionError에 너무 많이 당해서 BFS로 푸는 것을 선호한다.

---

3. 참고 사항

① BFS를 구현할 때 list 대신 collections 라이브러리에 있는 deque 자료구조를 사용하면 좋다.

BFS는 queue로 구현하므로 오른쪽에서 insert 하고 왼쪽에서 pop하는데 list와 deque의 차이는 다음과 같다.

 

list는 fixed size array로 구현되므로 왼쪽에서 pop하면 첫 번째 원소를 삭제시키고 모든 원소를 앞으로 이동시킨다.

따라서 list의 pop(0)의 시간복잡도는 O(n)이다.

하지만, deque는 doubly linked list로 구현되므로 왼쪽에서 pop하더라도 next와 prev만 살짝 만져주면 끝이다.

따라서 deque의 popleft()의 시간복잡도는 O(1)이다.

 

② 배열의 범위를 벗어나게 지렁이를 움직이면 안된다.

BFS의 새로운 좌표값(nx, ny)를 설정해서 queue에 넣어줄 때 이를 판별하는 과정이 필요하다.

 

③ board[x][y]에서 x는 세로고, y가 가로이다. (x는 행, y는 열을 의미한다.)

문제에서 주어진 가로길이 M은 y와 관련해서 이용해야 하고, 세로길이 N은 x와 관련해서 사용해야 한다.

---

4. 구현 코드

from sys import stdin
from collections import deque

def bfs(x, y):
    queue = deque([[x, y]])
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + move[i][0]
            ny = y + move[i][1]
            
            # 배열 범위 확인 + 배추밭인 경우
            if 0 <= ny < n and 0 <= nx < m and vege_list[nx][ny] == 1: 
                vege_list[nx][ny] = 0   # 미리 방문처리
                queue.append([nx, ny])  # 그리고 queue에 추가

t = int(stdin.readline())
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for _ in range(t):
    m, n, k = map(int, stdin.readline().split())
    vege_list = [[0] * n for _ in range(m)]

    # 배추밭을 입력 받는 라인
    for _ in range(k):
        x, y = map(int, stdin.readline().split())
        vege_list[x][y] = 1

    count = 0
    for i in range(m):
        for j in range(n):
            if vege_list[i][j] == 1:  # 배추밭이라면
                bfs(i, j)   # bfs로 인접한 땅을 모두 확인
                count += 1  # 지렁이 개수 하나 증가
    
    print(count)​