본문 바로가기
BOJ

백준(BOJ) 16946 벽 부수고 이동하기 4(Python)

by juLeena 2022. 7. 17.

문제 내용

 

BFS 문제.

모든 칸에 대해 탐색하는데, 벽이 아닌 칸에서 BFS를 진행한다.

인접한 모든 벽이 아닌 칸의 개수를 세고, 그 모든 칸에 동일한 고유 넘버를 지정해준 뒤 딕셔너리에 그 넘버에 해당하는 칸의 개수를 저장한다(해싱). visited에서 진행할 것이기 때문에 위의 예제에서 진행하면 다음과 같은 visited가 생성될 것이다.

000     010

000 -> 203

000     040

그 후에는 다시 모든 칸을 탐색하며 벽이 있는 칸인 경우 상하좌우의 칸이 벽이 아닌 경우 고유 넘버를 모두 저장하되, 이들이 중복되지 않도록 한다.

그 후 고유 넘버에 해당하는 칸의 개수를 모두 세서 입력받은 맵의 해당하는 칸에 더해주면 된다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n,m=map(int,input().split())
L=[list(map(int,list(input()))) for i in range(n)]
visited=[[0]*m for i in range(n)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
c=1
D={}
for i in range(n):
    for j in range(m):
        if not visited[i][j] and not L[i][j]:
            visited[i][j]=c
            queue=deque()
            queue.append([i,j])
            d=1
            while queue:
                x,y=queue.popleft()
                for k in range(4):
                    nx=x+dx[k]
                    ny=y+dy[k]
                    if 0<=nx<n and 0<=ny<m:
                        if not visited[nx][ny] and not L[nx][ny]:
                            visited[nx][ny]=c
                            d+=1
                            queue.append([nx,ny])
            D[c]=d
            c+=1
for i in range(n):
    for j in range(m):
        if L[i][j]:
            C=set()
            for k in range(4):
                nx=i+dx[k]
                ny=j+dy[k]
                if 0<=nx<n and 0<=ny<m:
                    if visited[nx][ny]:
                        C.add(visited[nx][ny])
            for k in C:
                L[i][j]+=D[k]
for i in range(n):
    S=''
    for j in range(m):
        S+=str(L[i][j]%10)
    print(S)

 

크게 어렵진 않았다.

해싱하고 set으로 중복 처리하는 게 파이썬이 아니라면 좀 까다로웠을 것 같다.

 

'BOJ' 카테고리의 다른 글

백준(BOJ) 2110 공유기 설치(Python)  (0) 2022.07.18
백준(BOJ) 1060 좋은 수(Python)  (0) 2022.07.18
백준(BOJ) 1082 방 번호(Python)  (0) 2022.07.17
백준(BOJ) 1039 교환(Python)  (0) 2022.07.16
백준(BOJ) 3366 수열 줄이기(Python)  (0) 2022.07.16