[알고리즘 문제 풀이][파이썬] 백준 1600번: 말이 되고픈 원숭이

백준 1600 문제 링크: https://www.acmicpc.net/problem/1600

📑 문제 설명
1. 원숭이가 0,0 에서 W, H로 이동해야 함
2. 단, 원숭이는 K 번만큼 말처럼 이동할 수 있음(말처럼 이동은 체스판의 나이트처럼 두 칸은 상하좌우로만, 그리고 마지막 한 칸은 대각선 방향으로 이동할 수 있음) 그 외에는 상하좌우로 한 칸씩만 이동 가능함
3. 이렇게 이동했을 때 원숭이가 갈 수 있는 최소 경로 구하기

입력: 첫째 줄에는 원숭이가 말처럼 이동할 수 있는 횟수 K가 주어지고 둘째 줄에는 가로 길이 W, 세로길이 H가 주어짐. 세번째 줄부터 H줄만큼 그래프가 주어짐

• 0은 갈 수 있고 1은 벽이라서 갈 수 없음
• 원숭이가 말처럼 이동할 경우 1을 만나더라도 뛰어넘을 수 있음

출력: 최소경로. 단, 도착점에 도달하지 못할 경우 -1 출력

💡 문제 해결 방법
알고리즘: dfs

알고리즘 선택 이유

• 한 분기에 들어가서 도착점까지 깊게 탐색해야 함
• 최선의 경로를 찾아야 하기 때문에 도달하고 끝이 아닌 다시 돌아와서 최적의 경로를 찾아야 함

예외처리

• 말처럼 간 횟수를 체크하는 변수 필요
• 말처럼 이동할 때는 1을 만나도 지나갈 수 있음(도달만 안됨)

스터디 내용

• map graph
• bfs
• x, y, horse, depth 네 인자를 사용
• 최단 거리는 BFS
• visit에 여기 올 때 까지 말처럼 몇 번 왔는지 체크

💻 코드

import sys
from collections import deque

k = int(sys.stdin.readline())
c, r = list(map(int, sys.stdin.readline().split()))
graph = []
for i in range(r):
    graph.append(list(map(int, sys.stdin.readline().split())))
visit = [[[False for x in range(k+1)] for x in range(c)]for x in range(r)]

queue = deque()
queue.append((0, 0, 0, 0)) # x, y, nhorse, dist
for i in range(k):
    visit[0][0][i] = True
# 현재 버택스에서 말처럼 이동한다 --> 나까지는 말처럼 이동하지 않고 다음 버택스가 말처럼 이동하는 것이므로 다음 버택스에 체크
def bfs(queue):
    while(queue):
        x, y, nhorse, dist = queue.popleft()
        monkeymove = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]
        if x == r-1 and y == c-1:
            print(dist)
            return
        horsemove = [[x-2, y+1], [x-2, y-1], [x-1, y+2], [x-1, y-2], [x+2, y+1], [x+2, y-1], [x+1, y+2], [x+1, y-2]]
        if nhorse < k: # 말처럼 이동할 수 있을 경우
            for nx, ny in monkeymove:
                if nx >= 0 and nx < r and ny >= 0 and ny < c:
                    if graph[nx][ny] == 0 and visit[nx][ny][nhorse] == False:
                        visit[nx][ny][nhorse] = True
                        queue.append((nx, ny, nhorse, dist+1))
            for nx, ny in horsemove:
                if nx >= 0 and nx < r and ny >= 0 and ny < c:
                    if graph[nx][ny] == 0 and visit[nx][ny][nhorse+1] == False:
                        visit[nx][ny][nhorse+1] = True
                        queue.append((nx, ny, nhorse+1, dist+1))
        elif nhorse >= k: # 말처럼 이동할 수 없을 경우
            for nx, ny in monkeymove:
                if nx>=0 and nx<r and ny>=0 and ny<c:
                    if graph[nx][ny] == 0 and visit[nx][ny][nhorse]==False:
                        visit[nx][ny][nhorse] = True
                        queue.append((nx, ny, nhorse, dist+1))

    print(-1)

bfs(queue)

💟 추가적으로 알게 된 점

• bfs 알고리즘에서 queue에 들어가는 버택스 들 중에 중복으로 삽입되지 않도록 신경쓰자.
• bfs + k번 가능 알고리즘에서는 k번 남았는가? > 갈 수 있는가? > 갈 수 있다면 지금 visit = True 그리고 queue에 삽입
• queue에 삽입하기 전에 visit을 true로 바꾸는 것을 잊지 말자