백준_7562_나이트의 이동

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

7562번: 나이트의 이동

 

문제요약)

-> 나이트가 한번에 이동할 수 있는 칸

나이트가 이동하려고 하는 칸이 주어졌을 때, 몇 번의 이동으로 목적지에 도달하는가?

 

 

 

 

입력)

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

 

출력)

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

풀이포인트)

문제에 주어진 그림에 따라 중심을 기준으로 나이트가 한번에 이동할 수 있는 칸을 좌표로 정리해보면,

1(왼1, 위2), 2(오1, 위2) 3(오2, 위1), 4(오2, 아1), 5(오1, 아2), 6(왼1, 아2), 7(왼2, 아1), 8(왼2, 위1)

따라서, 

dx = [-1, 1, 2, 2, 1,-1, -2, -2]

dy = [2, 2, 1, -1, -2, -2, -1, 1] 로 이동좌표를 설정 후 이동 반복문을 8번 수행해 반복 이동한다.

이동 시, 이전 값 +1 해서 저장하고, 목적지 좌표가 나오면 0이 아닌 1부터 시작했기 때문에 -1을 한 값을 리턴한다.

이동좌표로 인해 다른 유형의 문제라고 생각 할 수 있으나 목표지점에 도달하는게 목적이기에 bfs를 사용한다.

 

풀이)

from collections import deque #파이썬에 내장된 collections 에서 deque 수입.

# 나이트의 이동방향
dx = [-1, -2, -2, -1, 1, 2, 2, 1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]

n = int(input()) #테스트 케이스 개수 입력받기

#이동 좌표 설정
for i in range(n): #테스트 케이스 개수(n) 만큼 반복한다.
    l = int(input()) #체스판 한 변의 길이 입력받기
    graph = [] # 2차원 리스트를 통해 구현 할 체스판, 이동 횟수 기록
    for i in range(l): #체스판 크기 만큼 반복
        graph.append([0] * l) #(lxl)체스판이므로 [0]*l 만큼의 열 각 행마다 l번 추가
    #bfs
    queue = deque() #queue에 deque로 초기화
    x, y = map(int, input().split()) #'시작 위치' 입력
    w, z = map(int, input().split()) #'목표 위치' 입력
    queue.append((x, y)) #시작위치 deque에 입력
    while queue: #queue(deque) 내에 아무것도 남지 않을 때 까지 반복
        x, y = queue.popleft() #deque 맨왼쪽에 있는 좌표 꺼내서 x, y 위치에 매핑
        
        if x == w and y == z: # 꺼낸 좌표가 목표지점과 비교해서 같으면
            break #while문 탈출
        ''''시작위치를 계산이후에도 사용하려면, 시작 위치를 입력 받자마자 다른 변수에 저장한다.
        계산과정 진행으로 x, y 값은 계속해서 변경 될 것이다.
        현재위치가 목표위치에 도달하는 순간 while문 멈춘다.
        이 조건이 없는 경우 그래프의 모든 경우의 수 구하는 것이므로 시간초과로 이어질 수 있는 불필요한 연산이 많아진다.'''
        
        for i in range(8): #햔재 위치 기준으로 8방향 모두 구하기
            #현재 값 + 이동 값 = 신규위치
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= l or ny < 0 or ny >= l: #신규위치가 체스판 안에 존재하지 않는다면
                continue # 해당사항 건너뛰고 위 for문 반복한다.
            if graph[nx][ny] == 0: #한번도 방문하지 않았다면
                graph[nx][ny] = graph[x][y] + 1 #신규위치는 현재 좌표 +1값임
                queue.append((nx,ny)) #w,z좌표에서 값 출력한다.
    print(graph[w][z]) #나이트가 움직여야 할 좌표