[백준 30106] 현이의 로봇 청소기

문제 출처 : https://www.acmicpc.net/problem/30106

 

DFS나 BFS를 활용하여 풀 수 있는 플러드 필 문제 입니다. 하지만 DFS로 풀었을 때에는 시간초과가 발생했습니다. 같은 로직의 BFS로는 시간초과 없이 통과 되었습니다. 파이썬으로 문제를 풀 때에는 DFS보다는 BFS로 문제를 해결하는 습관을 들이는 것이 좋을 것 같습니다.

문제 이해하기

이 문제가 다른 플러드 필 문제와 다른 점은 연결이 되어있지 않아 여러 구역으로 나누어지는 것이 아니라 높이로 인해 건너갈 수 없어 여러 구역으로 나누어진다는 사실 입니다. 따라서 높이의 차를 통해 연결 여부를 따져야 합니다.

코드 작성하기

그럼 코드를 작성해 보겠습니다.

입력 받기

mii = lambda : map(int, input().split())

N, M, K = mii()

arr = []
for _ in range(N):
    row = list(mii())
    arr.append(row)

지도의 높이 N, 지도의 너비 M, 그리고 로봇 청소기가 이동할 수 있는 높이의 차이 K를 입력 받습니다. 다음으로 인접행렬 형태의 방의 지도를 입력 받습니다.

BFS 함수

from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)
visited = [[False] * M for _ in range(N)]

def bfs(y, x):
    q = deque()
    q.append((y, x))

    visited[y][x] = True

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

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

            if 0 <= ny < N and 0 <= nx < M:
                if not visited[ny][nx]:
                    if arr[y][x] - K <= arr[ny][nx] <= arr[y][x] + K:
                        visited[ny][nx] = True
                        q.append((ny, nx))

BFS 함수는 스택을 사용하는 것이 아니라 큐를 사용해야 합니다. 따라서 collections에 있는 deque를 import 해주었습니다.

다음으로 인접 행렬을 이동하기 위한 상, 하, 좌, 우의 좌표 dx, dy를 생성합니다. 그리고 지도의 방문 여부를 파악할 visited 리스트를 생성합니다.

BFS 함수는 먼저 q라는 deque를 생성합니다. 여기에 첫 번째 방문 지역을 넣어줍니다. 그리고 방문 지역을 visited 리스트에 방문 여부를 표시해 줍니다.

앞서 배웠던 BFS 로직과 같은 방식으로 코드를 작성합니다. 기존 코드와 다른 점은 높이 차이를 이용한 방문 여부 입니다. 새로 방문할 위치가 현재의 위치와 차이가 K 이하인지 아닌지를 확인하여 K 이하라면 방문을 하고, K를 넘어선다면 방문하지 않습니다.

solve 함수

def solve():
    cnt = 0
    for y in range(N):
        for x in range(M):
            if visited[y][x]:
                continue
            bfs(y, x)
            cnt += 1
    return cnt

print(solve())

solve 함수는 플러드 필 알고리즘으로 지도 전체가 몇개의 구역으로 나누어져 있는지 확인하는 함수 입니다. 지도의 처음부터 끝까지 탐색하면서 아직 방문하지 않은 곳을 만날때마다 cnt 값을 1씩 늘려줍니다. 최종적으로 얻은 cnt 값을 통해 지도를 몇 개의 구역으로 나눌 수 있는지 알 수 있습니다. 마지막으로 cnt 값을 리턴하여 출력하면 현이가 로봇 청소기를 몇 번 작동시켜 방의 모든 구역을 청소할 수 있는지 알 수 있습니다.

전체 코드

전체 코드를 확인해 보겠습니다.

from collections import deque

mii = lambda : map(int, input().split())

N, M, K = mii()

arr = []
for _ in range(N):
    row = list(mii())
    arr.append(row)

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)
visited = [[False] * M for _ in range(N)]

def bfs(y, x):
    q = deque()
    q.append((y, x))

    visited[y][x] = True

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

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

            if 0 <= ny < N and 0 <= nx < M:
                if not visited[ny][nx]:
                    if arr[y][x] - K <= arr[ny][nx] <= arr[y][x] + K:
                        visited[ny][nx] = True
                        q.append((ny, nx))

def solve():
    cnt = 0
    for y in range(N):
        for x in range(M):
            if visited[y][x]:
                continue
            bfs(y, x)
            cnt += 1
    return cnt

print(solve())