백준/ Gold 3 문제 , 백준 파이썬 1600 , 말이 되고픈 원숭이 [BFS]

백준/ Gold 3 문제 , 백준 파이썬 1600 , 말이 되고픈 원숭이 [BFS]

 

 

풀이 시간

 

 

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

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

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

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

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

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

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


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


<덧붙일 말>
Z에 담긴 값이 이동 횟수를 나타내게 풀려고 해봤는데 너무 안풀렸다. 그러다가 이동 횟수를 체크해주는 변수를 하나 더 넣었고 훨씬 수월하게 풀렸음

 

 

문제 출처

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

1600번: 말이 되고픈 원숭이

 

풀이

 

 

1. 기본 세팅

 

1. 상하좌우 움직임

 

2. 말의 움직임 (8가지)

 

3. K 입력받기

 

4. M,N 입력받기

 

5. N 행의 MAP 리스트 입력받기

 

6. 방문할 곳들을 체크해주는 visited 선언, 각 영역은 말의 제한된 이동횟수 만큼 갖는다. (K+1)

 

7. dq 선언

 

 

 

2. BFS 함수 선언 및 호출

처음에 X,Y, Z 로만 dq에 넣어가며 돌려봤는데, 예시는 잘풀렸지만 테스트 케이스에서 계속 틀렸다.

 

각 행열에 해당하는 영역은 K+1 만큼의 크기를 갖게 되는데 이는 말의 움직임을 한번 사용할때마다 Z+1 에 할당한다.

 

더이상 Z+1의 크기에 여유가 없는 영역은 이미 말의 움직임을 다 쓴 곳으로 이제 상하좌우 움직임으로만 움직여야 한다.

 

 

만약 K가 2로 주어진다면, 각 배열은 

 

[ [0][0][0], [0][0][0], [0][0][0], .... , [0][0][0]] 이런 식의 형태로 N 행 만큼 형성되어있을 것이다.

 

 

만약, 0행 0열에서 2행 1열로 말을 사용해 이동하게 되면,

 

[ [0][0][0], [0][0][0], [0][0][0], .... , [0][0][0]],

[ [0][0][0], [0][0][0], [0][0][0], .... , [0][0][0]],

[ [0][0][0], [0][1][0], [0][0][0], .... , [0][0][0]],

 

이렇게 Z+1 에 넣어주는 것이다.

 

2행 1열에서도 아직 말의 움직임이 한번 남았기 때문에 오른쪽에 여유공간이 하나 남게 된다.

 

이제 다음 말의 움직임을 사용하게 된다면  [0][0][1]   이런식으로 방문이 남을 것이다.

 

이제 오른쪽의 여유 공간이 더 없으니 이 상태가 되면 말의 움직임은 더 이상 사용할 수 없다.

 

 

초과하는 영역을 비교하지 않게 if 문으로 Z<K 인 값들만 통과시켜주고

 

for 문을 돌려주면된다.

 

 

이때, 중요한 점은 K만큼의 말의 움직임을 무조건 사용하는 것이 최적의 답은 아니다.

 

 

ex)

3
4 5
0 1 1 1
1 1 0 1
1 1 1 1
1 1 1 0
1 1 1 0

정답: 3

 

 

위의 반례는 말의 움직임을 두번만 사용해서 움직였을때 최적의 해답이 나온다.

 

 

dq에 넣은 값이 N-1,M-1 의 위치를 넣었을때가 가장 빠르게 이동할 수 있는 방법이고 그때 dq 에 넣어진 변수 O 를 통해 몇번만에 이 위치에 왔는지를 출력시켜주면 해답이다.

 

 

 

정답

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

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]
upDown=[1,2,2,1,-1,-2,-2,-1]
leftRight=[-2,-1,1,2,2,1,-1,-2]

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

def bfs():
    dq.append([0,0,0,0])
    while dq:
        X,Y,Z,O=dq.popleft()
        if X==N-1 and Y==M-1:
            print(O)
            exit(0)
        for i in range(N):
            print(visited[i])
        print()
        if Z<K:
            for j in range(8):
                mx,my=X+upDown[j],Y+leftRight[j]
                if 0<=mx<N and 0<=my<M:
                    if MAP[mx][my]==0:
                        if visited[mx][my][Z+1]==0:
                            visited[mx][my][Z+1]=visited[mx][my][Z]+1
                            dq.append([mx,my,Z+1,O+1])
        for i in range(4):
            mx,my=X+vertical[i],Y+parallel[i]
            if 0<=mx<N and 0<=my<M:
                if MAP[mx][my]==0 and visited[mx][my][Z]==0:
                    dq.append([mx,my,Z,O+1])
                    visited[mx][my][Z]=visited[X][Y][Z]+1
    print(-1)
    
bfs()