[백준] 1012번 - 유기농 배추 (DFS, BFS) - 결과 포함

www.acmicpc.net/problem/1012

1012번: 유기농 배추

이전에 풀었었던 '바이러스' 문제와 유사한 문제로 그래프에서 1로 이루어진 구역이 몇 개인지 구하는 문제이다.

 

먼저 1이 어디에 있을지 모르기 떄문에 모든 정점에서 출발해야 한다.

단, 이미 방문하거나 배추가 심어져 있지 않은, 0인 정점은 방문하지 않아도 된다.

 

정점에서 이동 가능한 방향은 상, 하, 좌, 우 4 방향이다.

방향을 미리 정해놓고 방문하지 않은 정점마다 반복문을 4번 돌면서 다음에 갈 정점을 정한다.

 

나는 BFS를 이용해서 문제를 해결했다.

방문하지 않았는데 배추가 심어져 있는 땅, 즉, 1이 들어있는데 아직 방문하지 않은 땅을 큐에 넣는다.

큐에 넣는 땅의 값을 0으로 바꾸어 다음번에 중복으로 방문하지 않도록 한다.

 

큐에서 하나씩 정점을 빼면서 4방향에 대해서 정점을 체크한다.

큐에 모든 점이 빠지면 BFS 함수에 주어진 카운트에 1을 더해서 리턴한다.

 

BFS에 주어지는 카운트는 초기에 0이다.

BFS는 배추가 심어진 땅일 때만, 그래프의 정점의 값이 1일 때만 수행하기 때문에 BFS에 들어간다는 것은 최소한 하나의 땅이 앞으로 감염될 것을 의미한다.

BFS는 인접한 모든 정점을 탐색하기 때문에 BFS에서 한번에 인접한 정점이 1개든 100개든 필요한 해충은 1마리가 증가한다.

그렇기 때문에 BFS는 수행될 때마다 기존의 카운트에서 1을 더한 값을 리턴한다.

 

모든 정점에 대해서 그래프를 검사한 후에 최종적으로 카운트를 리턴받아 출력했다.

 

[소스코드]

from collections import deque

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


def bfs(y, x, count):
    queue = deque()
    queue.append([y, x])
    graph[y][x] = 0

    while queue:
        y, x = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= m or ny >= n:
                continue
            if graph[ny][nx] == 0:
                continue
            if graph[ny][nx] == 1:
                graph[ny][nx] = 0
                queue.append([ny, nx])
    return count + 1

t = int(input())

for _ in range(t):
    cnt = 0
    m, n, k = map(int, input().split())

    graph = [[0] * m for _ in range(n)]

    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                cnt = bfs(i, j, cnt)
    print(cnt)