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

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

 

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

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

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

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

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

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

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


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


<덧붙일 말>
되게 어렵게 느껴졌던 문제이다. 스킬을 사용했는지를 따로 확인할 배열을 만들어서 체크하는 식으로까지는 작성하였지만, 그 이후 bfs 함수내에서 for 문을 작성하는데 시간이 오래걸렸음. 다른 블로그를 확인했더니 0을 두개씩 배정해서 체크하는 방법을 배움.

 

<문제 출처>

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

2206번: 벽 부수고 이동하기

 

 

틀린 풀이

 

 

처음에 작성한 풀이이다. 이 풀이를 작성하는데 꽤 걸렸는데, 예시는 잘 출력되지만 시간초과....

 

 

 

 

풀이

내가 생각하기에 정답 풀이의 핵심 코드는 이게 아닐까 싶다.

 

여태 BFS 문제를 풀때는 다 2차원 배열내에서 해결해서 3차원배열로 이렇게 풀 생각을 못했는데,

 

3번째 공간에 스킬 유무 표시를 해주는 것이다.

 

 

이 3차원배열로 사용하는 것만 아이디어가 떠올라도 훨씬 수월해진다.

 

나머지 로직은 

다른 bfs 문제들 처럼 작성해주면서 벽이 있을때와 그냥 통로일때를 구분해주면 된다.

 

그냥 통로일때는 그냥 이동시켜주고 벽으로 막혀져 있다면 z==0 인지 확인하여 스킬을 쓸 수 있는 상태인지 확인해준다.

 

그 후 스킬을 사용하게 되면 z 부분을 1로 바꿔줘서 스킬 사용했음을 표시 해준다.

 

 

 

 

 

 

정답

 

from collections import deque
import copy

vertical=[0,-0,1,-1]
parallel=[1,-1,0,0]
N,M=map(int,input().split())
MAP=[]
for i in range(N):
    MAP.append(list(map(int,input())))
MAP[0][0]=-1
visited=[[[0]*2 for _ in range(M)] for _ in range(N)]
visited[0][0][0]=1
result=[]

def bfs(x,y,z):
    dq=deque()
    dq.append([0,0,0])
    while dq:
        x,y,z=dq.popleft()
        if x==N-1 and y==M-1:
            return visited[x][y][z]
        for i in range(4):
            mx=x+vertical[i]
            my=y+parallel[i]
            if 0<=mx<N and 0<=my<M:
                if MAP[mx][my]==1 and z==0:
                    visited[mx][my][1]=visited[x][y][0]+1
                    dq.append([mx,my,1])
                elif MAP[mx][my]==0 and visited[mx][my][z]==0:
                    visited[mx][my][z]=visited[x][y][z]+1
                    dq.append([mx,my,z])
    return -1

print(bfs(0,0,0))