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

백준/ Gold 1 문제 , 백준 파이썬 16933 , 숫자고르기 [BFS]

 

 

풀이 시간

대충 3시간? 정도 쓴듯

 

치열했다.....

 

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

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

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

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

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

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

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


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


<덧붙일 말>
진짜 나를 힘들게 한 문제.... 괜히 골드 1 문제가 아님.
나름 벽부수는 시리즈를 풀어봐서 초반 풀이로는 정답이 잘 나오는듯 했는데 제출 시 시간초과를 해결하지 못했다.
이 코드 저 코드 돌려보고 지워보고 하면서 솔루션 참고하여 겨우 풀었는데 웬걸 생각만 조금만 바꾸면 허무하게 풀리는 문제였다...

참고로 pypy3 로 통과하였다.

 

 

문제 출처

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

16933번: 벽 부수고 이동하기 3

 

반례

 

2 4 2
0111
0110

 

정답

7

 

 

3 3 2
011
111
110

 

정답

-1

 

10 20 10
00100010110010001010
10110101110101011101
01101010001010011011
11101000011101011110
01100111011111000011
11000000001111111101
01100010010101111001
00000100110010100101
10011010100100010110
11011001110000010100

 

정답

30

 

 

5 3 10
001
110
011
010
010

 

정답 

7

 

 

 

 

 

풀이

 

 

1. 기본 세팅

 

이전 문제들 까지는 상하좌우를 

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]

을 사용해서 이동시켰는데, 위 코드처럼 쓰는게 더 직관적이고 간단하게 표기가 가능한것 같다.

 

앞으로 이 코드대로 사용해보겠음.

 

 

여기서 이전 문제들과 다른 점은 visited를 0으로 채워주는게 아닌 K+1로 채워준다는 점이다.

 

이걸 내가 처음에 생각하지 못한 부분인데, 이렇게 하게되면 뒤에서 나중에 더 빠른 경로가 있을때 이미 방문한 곳을 초기화시켜줄때 되게 용이하다.

 

while 문을 돌려가며 visited를 채워갈 것은 각 해당 위치에 도달했을때 벽부수기를 몇번 하였는가를 담아 줄 것이다.

 

굳이 해당 위치까지 몇번의 이동에 걸쳐서 왔는지를 visited에 담아줄 필요가 없다.

 

 

dq에는 네개의 값을 담아 줄건데, 앞에서부터 행, 열 , 벽부수기 횟수, 방문갯수

 

 

 

2. dq 돌리기

 

위에 dq에 담아줬던 값들을 초기값으로 dq를 돌려 나아간다.

 

이때 중요한 점 두가지가 있다.

 

if visited[mx][my]>Z:

하나는 이 코드인데, 초반에는 K+1 값들이 담겨있어서 첫 방문 위치들을 모두 방문해준다.

 

이후, 재방문 할 일이 생길때 현재의 경로가 이전 경로보다 더 빠른지를 이 코드를 통해서 같이 구별해내줄 수 있다.

 

어쩌면 이 문제에서 가장 중요한 부분이 이 부분인 것 같다.

 

이 코드로 판별만 해준다면 이제 이 if 문 내에는 이전문제들과 크게 다르지 않다.

 

 

또 다른 중요한 점은 밤 낮은 따로 변수를 두어 구분해줄 필요없이 방문횟수가 짝수인지 홀수인지로 판별하면 된다는 것이다.

 

초기 풀이에서는 1에다가 -1을 곱해가면서 풀이를 해봤는데 홀수 짝수로도 구별이 가능하겠다 싶었고 해당 코드를 적용해보았다.

 

참고로 밤에는 벽을 부술수 없으니 벽을 만날때는 그냥 이전위치에서 이동횟수만 +1 한 값을 dq에 넣어주면 된다.

 

 

X와 Y가 각각 N-1,M-1을 갖게되면 이전까지 이동횟수에 +1 한 값을 출력시키면 답이다.

 

만약 while문을 그냥 빠져나오게 되면 -1을 출력해주면 된다.

 

 

 

 

참고

https://cocook.tistory.com/153

[BOJ] 백준 16933 벽 부수고 이동하기 3 python

 

해당 블로그의 풀이를 참고하여 풀었다.

 

이전에는 visited에 0만 담아서 풀려고만했는데, K+1을 넣는 방법을 이 블로그 풀이를 통해 익혔다.

 

 

 

 

정답

 

 

pypy3로 통과

 

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

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

N,M,K=map(int,input().split())
MAP=[list(map(int,input().rstrip())) for _ in range(N)]
visited=[[K+1 for _ in range(M)] for _ in range(N)]

dq=deque()
dq.append([0,0,0,0])
visited[0][0]=0
while dq:
    X,Y,Z,C=dq.popleft()   
    if X==N-1 and Y==M-1:
        print(C+1)
        exit(0)
    for a,b in dr:
        mx,my=X+a,Y+b
        if 0<=mx<N and 0<=my<M:
            if visited[mx][my]>Z:
                if MAP[mx][my]==0:
                    visited[mx][my]=Z
                    dq.append([mx,my,Z,C+1])
                else:
                    if C%2==0:  # 낮 
                        if Z<K: 
                            visited[mx][my]=Z
                            dq.append([mx,my,Z+1,C+1])
                    else:  # 밤
                         dq.append([X,Y,Z,C+1])
print(-1)