Red Knight's Shortest Path (Python)[HackerRank]

출처 : https://www.hackerrank.com/challenges/red-knights-shortest-path/problem

Red Knight's Shortest Path | HackerRank

목차

1. 문제

2. 문제 해석

3. 소스 코드

---

문제(축약)

이 버전에서 레드나이트라는 새로운 말이 생겼다. 레드나이트는 상좌, 상우, 우, 하좌, 하우, 우 로 움직일 수 있습니다. 그림은 아래와 같습니다. 보드의 크기는 격자판으로 n*n입니다. 격자판은 0,0 부터 n-1, n-1까지 있습니다. 격자판의 크기n과 시작지점 is, js, 와 도착지점 ie, je가 주어질때 가장 빠르게 이동이 가능한 이동횟수와 경로를 출력합니다. 도착이 불가능하다면 'Impossible'을 출력합니다. 도착하는 횟수가 같다면 상좌, 상우, 우, 하좌, 하우, 우 의 우선순위로 출력합니다.

 

조건

격자판의 크기는 5와 200 사이입니다. n <= n <= 200 시작점과 도착점은 격자판 사이에 있습니다. 0 <= is, js, ie, je < n 시작점과 도착점의 위치는 다릅니다.

 

샘플 입력

7 6 6 0 1

 

샘플 출력

4 UL UL UL L

 

---

풀이

최단거리가 나왔으므로 BFS를 이용하여 풀면 되는 문제입니다. 주의해야 할점은 갔던위치를 다시가면 무한루프에 빠질 수 있으므로 갔던위치는 체크하여 더이상 이동하지 않습니다. 이동할때 우선순위를 주고나서 시작하면 처음 도착하는 순간이 가장 빠른 케이스가 됩니다. 저는 queue를 이용하여 풀건데 list를 큐처럼 이용하면 비용이 발생하므로 deque를 이용하여 풀었습니다.

---

소스코드

from collections import deque
 
dq = deque()
 
n = int(input())
s_y, s_x, e_y, e_x = map(int, input().split())
 
move = [(-2, -1, 'UL'), (-2, 1,'UR'), (0, 2, 'R'), (2, 1, 'LR'), (2, -1,'LL'), (0, -2,'L')]
 
dq.append((s_y, s_x, []))
 
answer = []
 
check_dict = {(s_y, s_x): True}
 
while len(dq) and not answer:
    y, x, _list = dq.popleft()
    for _y, _x, command in move:
        dy, dx = y + _y, x + _x
        if 0 <= dy < n and 0 <= dx < n:
            if check_dict.get((dy, dx), False):
                continue
            check_dict[(dy, dx)] = True
            if dy == e_y and dx == e_x:
                _list.append(command)
                answer = _list
                break
            dq.append((dy, dx, _list[:]+[command]))
 
if answer:
    print(len(answer))
    print(*answer)
else:
    print('Impossible')