[Python] 백준 7562 - 나이트의 여행

문제출처 : www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

알고리즘

일반적인 bfs문제이다. 다만, 최소값을 항상 유지시켜야함에 주의하자. 이미 최소 스텝이 아니었으면 최소가 아니니까.

deque를 쓸 경우 왼쪽부터 빼야, 최소에서 최소를 시도할수가 있다. popleft를 해줘야 한다.

따라서, visited를 만드는 것이 아니라 보드판 자체를 visited로 사용하는 것이 중요 포인트. 시작점이 0으로 시작하므로 -1을 default값으로 설정하여 풀었다.

 

코드(백준은 입력 부분 또한 넣어줘야 하나, 입력 부분은 생략한다)

 

from collections import deque
def bfs(s_x, s_y, e_x, e_y, chess):
    board = [[-1 for _ in range(chess)] for _ in range(chess)]
    direct = [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]
    board[s_x][s_y] = 0
    if s_x == e_x and s_y == e_y:
        return 0
    else:
        queue = deque()
        queue.append((s_x, s_y))
        while queue:
            curr_x, curr_y = queue.popleft()
            for i in range(0, 8):
                n_x = curr_x + direct[i][0]
                n_y = curr_y + direct[i][1]

                if n_x < 0 or n_x >= chess or n_y < 0 or n_y >= chess:
                    continue
                else:
                    if board[n_x][n_y] == -1:
                        board[n_x][n_y] = board[curr_x][curr_y] + 1
                        queue.append((n_x, n_y))
                    if n_x == e_x and n_y == e_y:
                        return board[n_x][n_y]