
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 |