[백준] 16949 - 벽 부수고 이동하기 4

벽 부수고 이동하기 4

생각 흐름

1. 벽을 만날 때마다 탐색을 돌린다.
2. 분명 시간초과가 날 것.
   왜냐하면 탐색은 $O(V)$인데 그걸 벽마다 돌리면 $O(V^2)$.
   $V$는 문제에서 $1000^2 = 1,000,000$이기 때문.
3. 0들이 모인 곳들을 클러스터라고 할 때, 그 클러스터가 닿는 벽들은 모두 그 클러스터에 닿을 수 있다.
4. 클러스터를 탐색하며 닿는 벽에다 그 클러스터의 크기를 더해주면 되지 않을까?
5. 클러스터를 모두 탐색해도 (0을 모두 방문하는 탐색을 해도) 탐색은 $O(V)$에서 그칠 것이니 시간초과가 나지 않을 것이다.
6. 벽을 방문여부를 체크해야 하나? 안 된다.
   -> 다른 클러스터에서도 벽에다 값을 더해줘야 하기 때문.
7. 벽 방문여부 체크를 안 하면 벽을 여러번 보게 되는데 그럼 나중에 벽에다 값을 더할 때 중복된다.
   -> 클러스터가 닿는 벽을 집합에 저장하자.

풀이

0인 부분에서만 탐색을 돌리며 방문 여부를 체크해준다. 벽은 가지 않는다.
단, 벽을 볼 때마다 그 벽의 위치를 집합에 저장한다. (중복해서 더해지는 것 방지)
탐색이 끝나면 해당 클러스터의 크기를 구할 수 있다.
집합에 있는 벽에 클러스터의 크기값을 더해준다.
각 벽에서 그 클러스터에 있는 곳을 모두 방문할 수 있다는 뜻이다.
이 탐색을 방문여부가 체크되지 않은 모든 0 위치에서 반복한다.

문제에서 값을 10으로 나눈 나머지로 하라고 했다.
그렇게 되면 벽에서 갈 수 있는 위치 수가 $n \times 10$ 여서 나머지가 $0$인 건지,
아니면 그 위치가 원래 벽이 아닌 건지를 모른다.
따라서 입력 받을 때 벽이 아닌 위치를 0이 아닌 -1로 받자.
나중에 출력할 때 -1을 0으로 출력해주면 된다.

DFS/BFS를 응용해서 시간복잡도를 줄이고 노드 방문을 최소화해서 해결하는 문제이다.

코드

import sys
from collections import deque


# 상하좌우
deltas = [(-1, 0), (0, 1), (1, 0), (0, -1)]

# 제수
DIVISOR = 10


def solution():
    N, M, field = get_input()

    visited = [[False for _ in range(M)] for _ in range(N)]

    for i in range(N):
        for j in range(M):
            # 벽이 아니면서 아직 방문되지 않은 곳을 계속해서 방문 (클러스터의 시작점)
            if field[i][j] == -1 and not visited[i][j]:
                visited[i][j] = True
                bfs((i, j), visited, N, M, field)

    # 정답 출력
    for line in field:
        sys.stdout.write("%s\n" % "".join([str(x) if x != -1 else '0' for x in line]))
        

def get_input():
    N, M = map(int, sys.stdin.readline().split())
    # 문제에서 값을 10의 나머지로 하라고 했으므로 
    # 벽이 아닌 곳의 0과 벽을 10으로 나눈 나머지 0을 구분하기 위해 벽이 아닌 곳을 -1로 받음
    field = [list(map(lambda x: 1 if x == '1' else -1, sys.stdin.readline().strip())) for _ in range(N)]
    return N, M, field
    
    
def bfs(start, visited, N, M, field):
    will_visit = deque([start])
    walls = set()
    cnt = 0

    # 클러스터 크기를 세면서, 클러스터 외곽의 벽 위치를 저장
    while len(will_visit) > 0:
        now_y, now_x = will_visit.popleft()
        cnt += 1

        for dy, dx in deltas:
            adj_y, adj_x = now_y + dy, now_x + dx

            if not (0 <= adj_y < N and 0 <= adj_x < M):
                continue
            if visited[adj_y][adj_x]:
                continue
            if field[adj_y][adj_x] != -1:
                # 인접 위치가 벽이면 해당 위치 저장
                walls.add((adj_y, adj_x))
                continue

            # 벽 아니면 이동
            visited[adj_y][adj_x] = True
            will_visit.append((adj_y, adj_x))

    # 저장된 벽 좌표에다 클러스터의 개수를 더해줌 (그 벽을 뚫었을 때 이동할 수 있는 곳의 개수)
    for wall_y, wall_x in walls:
        field[wall_y][wall_x] = (field[wall_y][wall_x] + cnt) % DIVISOR


solution()