[Python][백준] 16946번 벽 부수고 이동하기 4

https://www.acmicpc.net/problem/16946

공부 날짜 :2023.02.10
정답 참조 여부 : X

벽과 이동가능 영역이 주어질 때 어떤 벽이 없어졌을 때 그 위치에서 이동 가능한 영역을 찾는 문제이다.

---

각 벽에서 주변 이동가능한 영역을 계속 탐색하면 같은 영역을 중복해서 탐색하게 되기 때문에

반대로 이동가능한 영역을 먼저 탐색을 하고 각 벽에서는 4가지 방향에 있는 이동가능한 개수만 더해주면 된다고 생각했다. 하지만 결과는 시간초과

아무리 생각해도 로직은 맞는거 같아서 질문게시판을 찾아봤는데
나랑 비슷한 이유로 시간초과 난 사람이 꽤 많은듯 했다.

오답의 이유는 벽에서 4가지 방향의 이동가능한 개수를 더해줄때 같은 덩어리면 제외해야 했다.

0 0 0
0 1 0
0 0 0
# 이 경우 구분을 안해주면 4방향 모두에서 8씩 더해서 32가 나온다

그래서 덩어리의 개수만큼 리스트를 만들고 탐색이 된 덩어리에 해당하는 index에 True를 체크하는 방법을 사용했는데

이 경우 매번 벽에서 덩어리 개수만큼 리스트를 만들기 때문에 최악의 경우 2500억번의 연산이 나온다1000 * 1000의 맵에서 1과 0이 체스판처럼 번갈아서 나오면 벽의 개수는 50만개, 각각의 벽에서 50만개의 이동가능한 덩어리를 만든다 ㄷㄷ

그래서 체크하는건 딕셔너리로 만들어서 탐색시 해당 덩어리를 키로 1의 값을 저장했고,
dict.get()메소드를 이용해서 키가 있으면 1이 나오고 키가 없으면 0이 나오게 해서 처리를 해줬다.

즉 키가 있으면 안더하고 pass, 키가 없으면 해당 덩어리의 크기를 더하고 그 키를 딕셔너리에 추가해 줬다.

---

리스트를 만드는 것도 연산에 포함되는걸 상기시켜준 문제였다.

당연한 말이긴 하지만 리스트 생성과 관련해서는 크게 신경쓰지 않긴했다.

초기화를 생성으로 할 경우 이렇게 된다는걸 신경써야겠다.

소스코드

import sys
from collections import deque
from copy import deepcopy
input = sys.stdin.readline
##########################################################
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
##########################################################
n, m = map(int, input().split())

map_graph = [list(map(int, list(input().rstrip()))) for _ in range(n)]

answer = deepcopy(map_graph)

same_zero_area = [0, 0]

num = 2

# 모든 0들을 하나의 덩어리로 뭉치기, 번호는 덩어리 구분,
# same_zero_area에 번호 인덱스로 접근하면 덩어리 크기가 나옴
for i in range(n):
    for j in range(m):
        # 이동가능한 칸이 나오면 해당 칸을 기준으로 bfs로 같은 덩어리를 찾음
        if map_graph[i][j] == 0:
            map_graph[i][j] = num
            same_zero_area.append(1)

            visit = deque()
            visit.append((i, j,))

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

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

                    if nx < 0 or nx >= n or ny < 0 or ny >= m or map_graph[nx][ny] != 0:
                        continue

                    map_graph[nx][ny] = num
                    same_zero_area[num] += 1

                    visit.append((nx, ny,))

            num += 1

# for i in map_graph:
#     print(i)
#
# print(same_zero_area)
##########################################################
for i in range(n):
    for j in range(m):
        if map_graph[i][j] != 1:
            continue

        count = 1

        check = {}

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

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            if check.get(map_graph[nx][ny], 0):
                continue

            check[map_graph[nx][ny]] = 1
            count += same_zero_area[map_graph[nx][ny]]

        answer[i][j] = count % 10

for i in answer:
    print("".join(list(map(str, i))))