[백준 16946번] 벽 부수고 이동하기4(파이썬)

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

16946번: 벽 부수고 이동하기 4

처음 이 문제를 만났을 때에는
'이게 골드2?
이거 골드 5수준이잖아?'
하면서 쉽게 생각했습니다.
그리고 제출하자마자 시간초과.

제가 생각한 방식은 간단했습니다.
'지도돌다가 1만나면 거기서 bfs해준다'
이렇게 하면 예제는 통과하지만
시간초과가 납니다.
그리고 시간초과가 뜰 때
내가 뭘 생각하지 못하는구나 깨닫고 힌트를 얻어봤습니다.

https://ku-hug.tistory.com/153

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

아이디어는 바로
0을 미리 묶어준다입니다.
0을 그룹으로 묶은 후에
1를 만날때
'어떤 그룹과 인접하는지'
구한 후에
0의 갯수를 구하면
최소한 위에서 말한 1을 계속bfs해주는 방식보다는
시간 소요가 줄어듭니다.

#백준 16946번 벽 부수고 이동하기4
from collections import deque

dx=[0,0,1,-1]
dy=[1,-1,0,0]


N,M=map(int,input().split())
room=[]
for _ in range(N):
    put=input()
    tmp=[]
    for j in range(M):
        tmp.append(int(put[j]))

    room.append(tmp)


way=[[0]*M for _ in range(N)]
group=[[-1]*M for _ in range(N)]
mung=[0]*(M*N)
#1. 0을 각각 그룹화한다
numbers=0
visited = [[False] * M for _ in range(N)]
for x in range(N):
    for y in range(M):
        if room[x][y]==0 and visited[x][y]==False:
            cnt=1
            visited[x][y]=True
            q=deque()
            q.append([x,y])
            group[x][y]=numbers
            while q:
                px,py=q.popleft()

                for d in range(4):
                    nx=px+dx[d]
                    ny=py+dy[d]

                    if nx<0 or nx>=N or ny<0 or ny>=M:
                        continue
                    if visited[nx][ny]==True:
                        continue

                    if room[nx][ny]==1:
                        continue
                    if group[nx][ny]>=0:
                        continue

                    q.append([nx,ny])
                    visited[nx][ny]=True
                    group[nx][ny]=numbers
                    cnt+=1
            #mung이라는 리스트에 각각 넘버의 숫자를 넣음.
            mung[numbers]=cnt
            numbers+=1

#2 벽을 허물고 맡닺는 0의 갯수를 본다
for x in range(N):
    for y in range(M):
        if room[x][y]==0:
            continue
        way[x][y]+=1
        #집합으로 표시한 이유-->중복 없에기
        setting=set()
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if group[nx][ny]==-1:
                continue
            po=group[nx][ny]
            setting.add(po)

        for zero in setting:

            way[x][y]+=mung[zero]
        way[x][y]%=10

# for x in range(N):
#     print(" ".join(map(str,group[x])))
#
# print(mung)
for x in range(N):
    print("".join(map(str,way[x])))

pypy3로 통과한 코드입니다.

이 문제의 아이디어가 상당히 좋았습니다.
bfs를 구할 때
다른 관점에서 접근하는 걸 배웠습니다.