백준/ Gold 2 문제 , 백준 파이썬 16946 , 벽 부수고 이동하기 4 [BFS]

백준/ Gold 2 문제 , 백준 파이썬 16946 , 벽 부수고 이동하기 4 [BFS]

 

 

시간 초과 해결이 제일 빡세다

 

풀이 시간

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
접근 방법은 잘했는데 시간초과를 해결하는데 오래 걸렸다.
나는 MAP리스트에 인접 0의 갯수를 저장해서 나중에 그 값들을 더하는 식으로 짰는데,
이렇게 하면 시간 초과가 어디선가 발생한다.
약간의 로직만 바꿔서 인접0의 갯수는 dict를 사용해 저장하고 MAP에는 그룹의 번호만 남기는 식으로 풀어야한다.

 

 

 

 

문제 출처

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

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

 

초기 풀이

MAP리스트에 인접 0의 갯수들을 저장

시간초과 발생

 

 

풀이

 

 

1. 기본 세팅

 

1. 상하좌우

 

2. N 행의 MAP 리스트 선언

 

3. 그룹을 지정할 N 행의 리스트 선언

 

 

2. BFS

 

우선 재방문을 방지 하기 위해 visited 를 사용한다.

 

이때 bfs에는 x,y (행과 열의 위치) 와 C라는 그룹번호를 전달 받게 되는데

 

인접 0에다가 부여받은 그룹번호들을 S리스트에다가 할당해준다.

 

이후 총 몇개에다가 할당했는지 cnt 변수에 저장해두고

 

이 cnt를 return 시킨다.

 

 

3. BFS 호출 및 처리

각 그룹이 몇개의 인접 0들로 이루어져있는지를 dict 에다가 저장해둔다.

 

return 받은 cnt 값을 result 에 저장해두고 그룹 번호 c : result 값으로 dict 에 저장

 

 

 

4. 최종 리스트 생성

 

이제 S리스트에서 0인 값들은 MAP리스트에서 벽이 있던 자리와 같다.

 

이 부분들의 위치에서 각 인접 그룹번호에 맞는 값들을 더해주면된다.

 

이때 중복되게 더함을 방지 하기 위하여 set 을 사용한다.

 

 

4 5
11001
00111
01010
10101

 

예를 들면 (0행부터 시작) 2행 1열의 1은 왼쪽과 위쪽이 같은 그룹이다.

 

그래서 이 둘 중 하나의 값만 더해줘야하므로 set을 이용해 중복을 방지한다.

 

tmp 리스트에다가 더해줄 그룹 번호들을 넣어주고 이후 각 그룹번호들이 가지고 있는 각 인접 0들의 갯수들을 D에다가 더해 출력한다.

 

이때 인접 위치뿐만이 아닌 자기 자신 위치도 세줘야하기때문에 D+=1 을 더 해준 뒤 10으로 나눈 나머지를 출력한다.

 

 

정답

 

from collections import deque
import sys
input=sys.stdin.readline

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

N,M=map(int,input().split())
MAP=[list(map(int,input().rstrip())) for _ in range(N)]
S=[[0 for _ in range(M)] for _ in range(N)]

def bfs(x,y,C):
    dq=deque()
    dq.append([x,y])
    visited[x][y]=1
    cnt=1
    S[x][y]=C
    while dq:
        X,Y=dq.popleft()
        for a,b in dr:
            mx,my=X+a,Y+b
            if 0<=mx<N and 0<=my<M:
                if MAP[mx][my]==0:
                    if visited[mx][my]==0:
                        MAP[mx][my]=1
                        dq.append([mx,my])
                        visited[mx][my]=1
                        cnt+=1
                        S[mx][my]=C
    return cnt
c=1
MAX=0
dict={}
visited=[[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
    for j in range(M):
        if MAP[i][j]==0:
            result=bfs(i,j,c)
            dict[c]=result
            c+=1

for i in range(N):
    for j in range(M):
        D=0
        tmp=set()
        if S[i][j]==0:
            for a,b in dr:
                mi,mj=i+a,j+b
                if 0<=mi<N and 0<=mj<M:
                    if S[mi][mj]!=0:
                        tmp.add(S[mi][mj])
            for m in tmp:
                D+=dict[m]
            D+=1
        print(D%10,end='')
    print()