[백준] 16946번 벽 부수고 이동하기 4 - Python / 알고리즘 중급 1/3 - BFS (연습)

ByungJik_Oh·2025년 5월 20일

[Baekjoon Online Judge]

목록 보기

145/244

💡 문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

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

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

💭 접근

처음 이 문제를 보았을 때 입력으로 주어진 맵에서 1에 해당하는 모든 좌표에 대해 인접하는 0의 개수를 세고 그 위치에 0의 개수를 ans에 저장해주는 방식으로 구현하였지만 방문했던 곳을 계속해서 다시 방문해야하기 때문에 시간초과가 발생하였다.

따라서 1이 아닌 0인 좌표에 대해 인접하는 모든 0의 좌표를 구한 뒤, 각 0의 좌표에서 가로 세로로 인접하는 1의 좌표에대해 0의 좌표의 개수를 더해주는 방식으로 구현하였다.

우선 0인 좌표에 대해 BFS

for i in range(n): # 1
   for j in range(m):
       if graph[i][j] == 0 and not visited[i][j]:
           bfs(i, j)

먼저, 1이 아닌 0인 좌표에 대해 bfs함수를 호출해준다.

이 좌표를 기준으로 인접한 모든 0의 좌표를 zeros에 저장 (하나의 그룹)

while q: # 2
       x, y = q.popleft()
       zeros.append((x, y))

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

           if 0 <= nx < n and 0 <= ny < m:
               if not visited[nx][ny] and graph[nx][ny] == 0:
                   visited[nx][ny] = True
                   q.append((nx, ny))

이후, BFS를 사용하여 기준이 되는 0에서 인접한 모든 0의 좌표를 zeros에 저장해준다. 이를 0으로만 이루어진 하나의 영역(그룹)으로 생각하면 된다.

이 그룹에 속한 모든 0과 인접한 1(벽)의 좌표를 wall에 저장

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

           if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
               wall.add((nx, ny))

위에서 만든 0의 영역에 대해 인접한 모든 1(벽)의 좌표를 저장한다.

그룹과 인접한 벽에 그룹의 크기(len(zeros))를 더해준다.
```
for x, y in wall: # 4
       ans[x][y] += len(zeros)
```
이때 각각의 벽에 그룹의 크기만큼 더해준다. 이와 같은 작업을 모두 마치면 중복되지 않게 방문하며 영역이 크기를 구할 수 있게 된다.

벽에 대한 초기값도 0이기 때문에 출력전에 1을 더해준다.

for i in range(n): # 5
   for j in range(m):
       if graph[i][j] == 1:
           ans[i][j] += 1
           ans[i][j] %= 10

마지막으로, 벽도 이동할 수 있는 칸 중 하나이기 때문에, 1을 더해준다.

📒 코드

from collections import deque

def bfs(start_x, start_y):
    q = deque()
    q.append((start_x, start_y))
    zeros = []
    wall = set()
    visited[start_x][start_y] = True

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

    while q: # 2
        x, y = q.popleft()
        zeros.append((x, y))

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

            if 0 <= nx < n and 0 <= ny < m:
                if not visited[nx][ny] and graph[nx][ny] == 0:
                    visited[nx][ny] = True
                    q.append((nx, ny))

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

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                wall.add((nx, ny))

    for x, y in wall: # 4
        ans[x][y] += len(zeros)

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
ans = [[0 for _ in range(m)] for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]

for i in range(n): # 1
    for j in range(m):
        if graph[i][j] == 0 and not visited[i][j]:
            bfs(i, j)

for i in range(n): # 5
    for j in range(m):
        if graph[i][j] == 1:
            ans[i][j] += 1
            ans[i][j] %= 10

for i in range(n):
    print(*ans[i], sep='')