[백준] 유기농 배추

문제

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

TC

2차원 배열의 높이 H, 너비 W라고 했을 때
O(HW)

Idea

네 방향으로 이동이 가능하므로 각 영역당 한 마리의 배추흰지렁이를 배치하면 해결할 수 있다.
즉, 1로 되어있는 영역이 몇 개 있는지 구하는 문제이므로 BFS 또는 DFS를 통해 풀 수 있다.

code (Python)

DFS 풀이

import sys
sys.setrecursionlimit(10000)

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return False

    if graph[x][y] == 1:
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    return False

t = int(input())
for _ in range(t):
    # n=가로, m=세로, k=배추의 개수
    n, m, k = map(int, input().split())
    graph = [[0 for _ in range(m)] for _ in range(n)]

    # 배추 위치 정보 입력
    for _ in range(k):
        x, y = map(int, input().split())
        # 배추가 있으면 1로 표시
        graph[x][y] = 1

    # 배추흰지렁이 최소 마리 수
    bug = 0
    for i in range(n):
        for j in range(m):
            # 배추가 있으면 dfs 탐색
            if graph[i][j] == 1:
                dfs(i, j)
                bug += 1

    print(bug)

BFS 풀이

from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def bfs(x, y):
    global bug

    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0
    bug += 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위 내이고, 배추가 있는 칸이라면 0으로 바꾸기
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 1:
                    graph[nx][ny] = 0
                    queue.append((nx, ny))

t = int(input())
for _ in range(t):
    # n=가로, m=세로, k=배추의 개수
    n, m, k = map(int, input().split())
    graph = [[0 for _ in range(m)] for _ in range(n)]
    # 배추 위치 정보 입력
    for _ in range(k):
        x, y = map(int, input().split())
        # 배추가 있으면 1로 표시
        graph[x][y] = 1

    # 필요한 벌레 수
    bug = 0
    for i in range(n):
        for j in range(m):
            # 해당 위치에 배추가 있으면, 연결된 배추 0으로 바꾸고 벌레 한 마리 증가
            if graph[i][j] == 1:
                bfs(i, j)

    # 필요한 최소의 배추흰지렁이 마리 수
    print(bug)

self code review

다른 문제들 중에서는, 원본 그래프를 변경하지 않기 위해 visited로 그래프와 똑같은 크기의 리스트를 선언하고 방문한 노드인지 아닌지 체크하여 중복된 방문을 방지하는데, 해당 문제에서는 단지 배추 구역만 세면 되므로 원본 리스트를 변경해도 상관없었다.

이것 또한 기본 그래프 탐색 문제여서 어려움 없이 해결했다.