백준/ Gold 5 문제 , 백준 파이썬 17836, 공주님을 구해라! [BFS]

백준/ Gold 5 문제 , 백준 파이썬 17836, 공주님을 구해라! [BFS]

 

 

풀이 시간

 

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

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

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

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

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

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

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


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


<덧붙일 말>
리턴값을 처리하는 부분에서 푸는 시간이 좀 걸렸다

 

 

문제 출처

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

17836번: 공주님을 구해라!

 

 

풀이

 

1. 기본 세팅

 

1. 상하좌우

 

2. N,M,T 입력 받기

 

3. N행의 MAP 리스트를 입력 받는데 이때, 그람의 위치는 -1 로 변경 시켜준다. 이유는 뒤에서 설명하겠다.

 

 

 

2. BFS

 

우선 시작 값은 0,0 부터다. 

 

 

이동하면서 두가지를 확인할 것이다.

 

1. 칼을 가지고 도착지점에 가는 경우

 

2. 칼을 가지러가지 않고 그냥 도착지점에 도달하는 경우

 

 

이제 0 위치로 한개씩 방문 갯수를 늘려가면서 이동한다.

 

이때, 아까 -1 로 바꾼 칼을 만나게 되는 경우를 분류 한다.

 

여기서 -1 로 바꾼 이유가 있다. 2로 그냥 냅두게 되면 0으로 이동하는 칸에서 2를 또 만들게 되어 중간부터 어느 위치가 칼인지를 모르게 된다.

 

그러므로 위치를 이동해도 나올 수 없는 숫자인 -1로 바꿔준 것이다.

 

이 칼의 위치로 이동하면 체크해줄것이 

 

1. 이 칼의 위치로 오기까지 걸린 방문 횟수

 

2.  칼의 위치로부터 N-1,M-1 까지 이동했을때의 방문횟수이다.

 

이때 2번의 경우 연산이 쉬워지는데

 

칼을 갖게되면 벽을 몇개든 부실수 있기때문에 칼의 위치로부터 도착지점 까지의 방문 횟수는 무조건

(N-1-mx)+(M-1-my)

이다.

 

이 값을 칼의 위치까지로 오기까지의 값이랑 합해주면 칼을 가지고 도착지점까지 갈 수 있는 최소의 방문 횟수이다.

 

 

여기서 끝나는 것이 아닌 칼을 만약 가지고 가지 않고 그냥 도착지점까지 가는 경우를 세줘야 한다.

 

이 경우는 N-1,M-1 칸에 저장될 값이므로 

 

이 위치에 도달하게 되면 이 값과 방금전 구했던 칼을 가지고 도착할 방문 횟수를 한꺼번에 담아 리턴한다.

 

 

3. BFS 호출 및 처리

 

리턴 값을 result 에 담아주고 이제 분류 해준다.

 

1. 칼을 가지고 도착지점에 가는 경우

 

2. 칼을 가지러가지 않고 그냥 도착지점에 도달하는 경우

 

이 두 경우중에서 0 인 값이 있는지 분류 해주고 

 

둘다 0이 아니라면 둘중에 최소값을 tmp에 넣어준다.

 

 

이제 T와 비교해주고 구출할 수 있는건지 아닌지를 판별해주면 된다.

 

 

정답

 

 

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

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

N,M,T=map(int,input().split())
MAP=[]
check=False
for i in range(N):
    L=list(map(int,input().split()))
    if check==False:
        for j in range(M):
            if L[j]==2:
                L[j]=-1
                check=True
    MAP.append(L)

def bfs():
    dq=deque()
    dq.append([0,0])
    MAP[0][0]=1
    S=0
    while dq:
        X,Y=dq.popleft()
        for a,b in dr:
            mx,my=X+a,Y+b
            if mx==N-1 and my==M-1:
                return [MAP[X][Y],S]
            if 0<=mx<N and 0<=my<M:
                if MAP[mx][my]==0:
                    MAP[mx][my]=MAP[X][Y]+1
                    dq.append([mx,my])
                elif MAP[mx][my]==-1:
                    S=MAP[X][Y]
                    MAP[mx][my]=MAP[X][Y]+1
                    S+=(N-1-mx)+(M-1-my)
                    dq.append([mx,my])
    return [0,S]

result=bfs()

if result[0]==0:
    tmp=result[1]
elif result[1]==0:
    tmp=result[0]
else:
    tmp=min(result)
    
if result==[0,0] or tmp>T:
    print('Fail')
else:
    print(tmp)