문제

[백준] 벽 부수고 이동하기 4 (Gold 2)

요약

N*M 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳을, 1은 이동할 수 없는 벽을 나타낸다. 각각의 벽에 대해서 다음을 구해보자.

  • 벽을 부수고 이동할 수 있는 곳으로 변경한다.
  • 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

분류

  • BFS
  • DFS

풀이

1. 내 풀이 (BFS)

나는 0을 기준으로 생각했다. 1을 기준으로 생각하려면, 0의 면적을 미리 계산해 전처리를 하지 않으면 같은 공간을 여러 번 탐색해야 하기에 시간 초과가 나왔다.

각 0을 중심으로 인접한 곳을 탐색한다. 벽을 만나면 좌표를 세트에 튜플 형태로 저장해 두었다가 인접한 0의 면적만큼 더해주었다. 하나의 벽에 여러 개의 0들이 인접할 수 있기 때문에 중복을 처리하기 위해 세트를 사용했다.

시간 복잡도는 O(NM)이다. (O(N^2))


import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, list(input().rstrip()))) for _ in range(n)]
ans = [a.copy() for a in arr]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
visit = [[False] * m for _ in range(n)]
for zero_r in range(n):
    for zero_c in range(m):
        if arr[zero_r][zero_c] == 0 and not visit[zero_r][zero_c]:
            s = set()
            queue = deque([(zero_r, zero_c)])
            cnt = 0
            one_list = []

            while queue:
                r, c = queue.popleft()

                if visit[r][c]:
                    continue
                visit[r][c] = True
                cnt += 1

                for i in range(4):
                    nr, nc = r + dy[i], c + dx[i]

                    if 0 <= nr < n and 0 <= nc < m and not visit[nr][nc] and arr[nr][nc] == 0:
                        queue.append((nr, nc))

                    elif 0 <= nr < n and 0 <= nc < m and arr[nr][nc] == 1:
                        one_list.append((nr, nc))

            for y, x in one_list:
                if (y, x) not in s:
                    ans[y][x] = (ans[y][x] + cnt) % 10
                    s.add((y, x))

for a in ans:
    for b in a:
        print(b, end="")
    print()

2. DFS

  • BFS에서의 큐를 스택으로만 바꿔주면 된다.