벽 부수고 이동하기 4 ( 16946 번 )

16946번: 벽 부수고 이동하기 4

 

---

🧠 알고리즘

• Flood Fill (BFS 기반)
• 맵에서 0(이동 가능)으로 연결된 영역을 BFS로 탐색하며 같은 영역을 하나의 번호로 채우고 크기(count)를 기록.
• 이렇게 기록한 영역 정보를 바탕으로 벽 주변 이동 가능한 칸 수를 계산.

 

 

✔️ 동작 방식

• _search_cr에서 BFS를 이용해 0 영역을 모두 탐색하고, 영역마다 번호(num)와 크기(count)를 저장.
• _main에서 각 벽 칸에 대해 상하좌우 인접한 서로 다른 영역의 크기를 합산.
• 합산한 값에 1을 더해 벽을 부순 후 이동 가능한 총 칸 수 계산.
• 최종 결과에서 벽 칸은 10으로 나눈 나머지(% 10), 빈 칸은 0 그대로 출력.

---

 

🧾 코드

import sys
from collections import deque

def _search_cr(n, m, map_list):
    answer = {}
    num = 2
    
    for i in range(n):
        for j in range(m):
            if map_list[i][j] == 0:
                count = 1
                map_list[i][j] = num
                queue = deque([(i, j)])

                while queue:
                    x, y = queue.popleft()
                    for n_x, n_y in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
                        if 0 <= n_x < n and 0 <= n_y < m and map_list[n_x][n_y] == 0:
                            count += 1
                            map_list[n_x][n_y] = num
                            queue.append((n_x, n_y))
                            
                answer[num] = count
                num += 1

    return answer


def _main(n, m):
    answer = [[0]* m for _ in range(n)]
    map_list = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
    search_dict = _search_cr(n, m, map_list)

    for i in range(n):
        for j in range(m):
            if map_list[i][j] == 1:
                adjacent = set()
                for n_x, n_y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                    if 0 <= n_x < n and 0 <= n_y < m and map_list[n_x][n_y] != 1:
                        adjacent.add(map_list[n_x][n_y])
                
                point = 1 + sum(search_dict[num] for num in adjacent)
                answer[i][j] = point % 10  # 최종 % 10

    for row in answer:
        print(''.join(map(str, row)))

n, m = map(int, sys.stdin.readline().rstrip().split())
_main(n, m)

---

 

⏱️ 시간 복잡도

_search_cr(n, m, map_list) : BFS 탐색 ( 이차형 시간 복잡도 )
for i in range(n) : 벽 주변 영역 탐색 ( 이차형 시간 복잡도 )
    for j in range(m)

해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )