[백준] Python 16948번 데스 나이트 실버1 - 그래프

문제 : https://www.acmicpc.net/problem/16948

접근 방법

1. 목적지에 갈 수 있는 경우의 수를 생각한다.
2. 몇 번 이동했는지 체크를 하며 가장 적은 횟수를 출력하면 된다.

• queue에 현재 위치, 이동 횟수를 담는다.
• 현재 위치를 방문했다고 체크한다.
• 움직일 수 있는 6가지의 방법으로 움직여 보고 움직일 때마다 이동 횟수를 증가시킨다. 여기서 밖으로 나가는 부분은 고려해줘야 한다.

풀이

N = int(input())
r1, c1, r2, c2 = map(int,input().split())
visited = [[0] * N for _ in range(N)]

def bfs(y, x):
    q = []
    q.append((y, x, 0)) 
    flag = False
    # 갈 수 있는 방향
    dy = [-2, -2, 0, 0, 2, 2]
    dx = [-1, 1, -2, 2, -1, 1]

    while len(q) != 0:
        # 현재 위치
        cur_y = q[0][0]
        cur_x = q[0][1]
        # 몇 번 움직였는지 count
        dist = q[0][2]
        # 갔던 곳 방문 체크
        visited[cur_y][cur_x] = 1
        q.pop(0)

        for i in range(6):
            ny = cur_y + dy[i]
            nx = cur_x + dx[i]
            # 목적지와 같다면 종료
            if ny == r2 and nx == c2:
                flag = True
                print(dist + 1)
                visited[ny][nx] = 1
                break

            if ny >=0 and nx >= 0 and ny < N and nx < N:
                if visited[ny][nx] == 0:
                    visited[ny][nx] = 1
                    q.append((ny ,nx, dist + 1))

        if flag:
            break

bfs(r1, c1)
if visited[r2][c2] == 0:
    print(-1)