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

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

플러드 필 + BFS 문제이다.

일단 먼저 말해두자면 (x, y)좌표가 1일 때마다 bfs를 돌리면 시간 초과가 나온다.

그래서 0끼리 뭉쳐있는 곳끼리 값을 설정 해줘야 한다.

다 설정했으면 그때 for문을 다시 돌려 벽이 있는 곳이 나온다면 리스트를 하나 만든다음, 상하좌우에 0이 있다면 플러드필을 이용해 저장한 값을 리스트에 저장해준다.

그다음 set을 이용해 중복 제거 해주고 값을 더해주면 끝난다.

코드가 너무 길어서 메인 코드 가독성을 해치기 때문에 따로 함수 2개를 구현하였다.

bfs 함수는 0끼리 뭉쳐있는 곳을 묶어준 후 리스트에 넓이를 저장해주는 함수이고, Sum 함수는 플러드 필을 다하고 벽 좌표에 출력할 값을 구하는 함수이다.

코드 확인

def bfs(a,b):
    ans=1
    S[a][b]=t
    q=deque([(a,b)])
    while q:
        x,y=q.popleft()
        for k in range(4):
            nx,ny=x+dx[k],y+dy[k]
            if 0<=nx<n and 0<=ny<m and D[nx][ny]=='0' and S[nx][ny]==-1:
                ans+=1
                S[nx][ny]=t
                q.append((nx,ny))
    return ans
def Sum(x,y):
    G=[]
    for k in range(4):
        nx,ny=x+dx[k],y+dy[k]
        if 0<=nx<n and 0<=ny<m and D[nx][ny]=='0':
            G.append(S[nx][ny])
    ans=sum([P[k] for k in [*set(G)]])+1
    return ans%10
from collections import deque
n,m=map(int,input().split())
D=[input() for _ in range(n)]
S=[[-1]*m for _ in range(n)]
K=[[0]*m for _ in range(n)]
P=[]
t=0
dx,dy=[0,0,1,-1],[1,-1,0,0]
for i in range(n):
    for j in range(m):
        if D[i][j]=='0' and S[i][j]==-1:
            P.append(bfs(i,j))
            t+=1
for i in range(n):
    for j in range(m):
        if D[i][j]=='1':
            K[i][j]=Sum(i,j)
for i in range(n):
    print(''.join(map(str,K[i])))