Baekjoon 16946. 벽 부수고 이동하기 4 / Python

16946. 벽 부수고 이동하기 4

난이도 : 골드 2
소요 시간 : 40분
날짜 : 2024.12.24
언어 : 파이썬
알고리즘 유형 : bfs, 그래프

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

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

2. 해결 방식

시간 줄이기*

1. 맵의 크기가 최대 1000 * 1000 이기 때문에 그냥 bfs를 돌리면 시간복잡도가 10^12로 시간초과가 난다.
2. 시간을 줄이기 위해 집합과 인덱싱을 사용한다.
3. 인덱싱 -> 유니온파인드 알고리즘과 유사한 방법

풀이

1. 벽인 곳을 찾는다.
2. 벽의 상하좌우에서 벽이 아닌 곳을 찾는다.
3. 벽이 아닌 곳에서 bfs를 돌린다.
   • 이 때, bfs를 돌려서 이동가능한 공간에 인덱스 번호를 부여하고,
   • 인덱스 번호에 맞는 리스트를 만들어준다.
   • bfs 종료 후 계산된 값을 리스트[인덱스 번호]에 입력해준다.
4. 벽이 아닌 곳에 이미 인덱스가 있다면, bfs를 돌릴 필요 없이, 리스트에서 그 인덱스에 해당하는 원소를 찾으면 된다.

3. 정답 코드

import sys
sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")

# input = sys.stdin.readline

from collections import deque as dq

n, m = map(int, input().split())

maze = [list(input()) for _ in range(n)]

direction = [
    (0, 1), (0, -1), (1, 0), (-1, 0)
]

res = [[0] * m for _ in range(n)]    # 결과값을 저장할 리스트
checked = [[-1] * m for _ in range(n)]    # checked[i][j] == i, j가 가지는 인덱스 값
ans = []    # ans[i] == i번 인덱스의 bfs 계산 값

def bfs(a, b, idx):
    q = dq()
    q.append((a, b))

    checked[a][b] = idx
    cnt = 1

    while q:
        x, y = q.popleft()
        for dx, dy in direction:
            nx, ny = x + dx, y + dy
            if nx in range(n) and ny in range(m):
                if maze[nx][ny] == '0' and checked[nx][ny] == -1:
                    checked[nx][ny] = idx    # 인덱스 번호 부여
                    q.append((nx, ny))
                    cnt += 1
    return cnt

idx = 0
for i in range(n):
    for j in range(m):
        if maze[i][j] == '0' and checked[i][j] == -1:
            ans.append(bfs(i, j, idx))    # ans[인덱스] = 계산값
            idx += 1

for i in range(n):
    for j in range(m):
        if maze[i][j] == '1':
            area_arr = set()
            for di, dj in direction:
                ni, nj = i + di, j + dj
                if ni in range(n) and nj in range(m) and maze[ni][nj] == '0':
                    area_arr.add(checked[ni][nj])    # 벽 주변 이동가능한 공간

                cnt = 1    # 자기자신 포함
                for area in area_arr:
                    cnt += ans[area]
                res[i][j] = cnt % 10

for arr in res:
    print(''.join(map(str, arr)))