백준 1012번 : 유기농 배추 in Python

1012번: 유기농 배추

 

www.acmicpc.net

위 문제는 배추밭에 필요한 배추흰지렁이의 수를 구하는 문제인데, 배추흰지렁이 한 마리를 배추가 있는 곳에 놓으면 그 배추와 인접해있는 모든 배추를 해충으로부터 보호할 수 있다는 특징을 가지고 있다. 따라서 위 문제는 어떤 하나의 배추와 인접하는 모든 배추들을 하나의 집합으로 볼 때 총 집합의 개수를 묻는 문제와 같고, 이는 그래프 탐색을 통해 쉽게 구할 수 있다.

우선 가로 길이와 세로 길이, 그리고 배추의 개수를 이용해 배추밭을 행렬로 만들어야 한다. 이를 위해 세로 길이가 행의 개수, 가로 길이가 열의 개수가 되는 행렬을 만들고 배추의 좌표값을 이용해 배추가 있는 곳의 값을 1로 한다. 이렇게 만든 행렬을 field라 하자.

그러면 행렬의 모든 원소들을 순회하면서 1이 있는 곳을 찾고, 1을 찾으면 그 1과 인접한 1들의 집합을 찾은 것으로 간주해 필요한 배추흰지렁이 개수를 하나 더해주고 그 1에 대해 DFS나 BFS를 실행해 1와 인접한 모든 1들을 -1로 바꿔서 이후 이 집합에 한 번 더 방문하는 일이 일어나지 않도록 한다. 

DFS는 상하좌우 방향으로 탐색이 가능하므로 dx 배열과 dy 배열을 적절히 이용해 네 방향으로 DFS를 재귀적으로 호출하는 방식으로 하되, 모서리 부분의 경우 특정 방향으로 가는 것이 불가능하므로 x좌표와 y좌표가 0 <= x < M, 0 <= y < N이 될 때만 DFS를 재귀적으로 호출한다. 그리고 행렬을 만들고 이 행렬에 대한 좌표를 나타낼 때 field[x][y]가 아니고 field[y][x]임에 유의해야 한다. 왜냐하면 행렬을 코드로 나타낼 때 첫 번쨰 인덱스가 몇 번째 행인지(y좌표에 해당한다)를 나타내고, 두 번째 인덱스가 몇 번째 열인지(x좌표를 나타낸다)를 나타내기 때문이다.

이를 코드로 구현하면 다음과 같다.

# 동서남북 방향을 나타내기 위한 배열
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# DFS 구현 함수
def DFS(y, x):
    global M
    global N
    if field[y][x] <= 0: return
    field[y][x] = -1
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if 0<=next_x<M and 0<=next_y<N:
            DFS(next_y, next_x)
    return
T = int(input())    
for _ in range(T):
    # 총 배추흰지렁이 개수
    count = 0
    M, N, K = map(int, input().split())
    field = [[0]*M for _ in range(N)]
    for _ in range(K):
        x, y = map(int, input().split())
        # x좌표와 y좌표를 바꿔 넣어야 함에 주의한다.
        field[y][x] = 1
    for i in range(N):
        for j in range(M):
            if field[i][j] == 1:
                DFS(i, j)
                count += 1
    print(count)