[백준] 나이트의 이동(7562번)

lsh9672·2022년 2월 9일

백준

baekjoon

목록 보기

9/21

[출처] https://www.acmicpc.net/

알고리즘 분류 : 그래프 이론, 그래프 탐색

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

[출처] https://www.acmicpc.net/problem/7562

입력

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

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

출력

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

예제 입출력

접근

이 문제는 격자형 그래프에서 탐색을 하는 문제이다
각 칸을 노드로 보고, 나이트가 이동할수 있는 위치들을 인접노드로 생각하면, 그래프로 보는데에는 문제가 없을 것이라고 생각한다.

아래는 접근 아이디어이다.

1. 그래프 판단

주어진 체스판(격자형 그래프)에서 시작노드를 루트로 생각하고, 나이트가 이동할수 있는 총 8가지 위치를 인접노드라고 생각한다.

2. 탐색 알고리즘 선정

그래프라는 것을 알았으면 bfs/dfs 두가지 방식이 탐색방법으로 생각날것이다.
이중 bfs방법을 이용해서 갈수 있는 모든 노드를 탐색한다.

3. 그래프 만들기

격자형 그래프의 모든 값은 0으로 만들어서 방문을 하면 1로 표시하여 중복탐색을 방지하도록 한다.

4. 탐색

탐색 과정은 일반적인 그래프 탐색과 다른것이 없다.
우선 현재노드(좌표)에서 나이트가 이동할수 있는 8개의 좌표를 아래 코드에서 dy,dx로 정의해준다.

이렇게 정의를 해두면 탐색이 필요한 큐에서 하나의 노드를 꺼내고 그에 인접한 노드들은 반복문을 돌면서 꺼낸 현재노드에 dy,dx를 더해주면 다음 노드가 된다.

현재노드로 부터 갈수있는 노드(그래프에서 값이 0)로 이동하고 이동시 마다 +1해서 이동 횟수를 카운트 해준다.

목적지에 도달하면 카운트한 값을 반환해주고 탐색을 종료해준다.

import sys
from collections import deque


'''bfs 정의'''
#나이트의 시작노드와 도달하고자 하는 노드, 체스판 정보를 인자로 받음
def bfs(start_node:tuple,end_node:tuple,graph:list) -> int:

    #다음노드 이동
    dy = [-1,1,-1,1,2,2,-2,-2]
    dx = [2,2,-2,-2,-1,1,-1,1]

    #방문처리는 체스판에 하면되기 때문에 따로 처리용 리스트를 만들필요는 없음
    need_visited = deque(list())

    #시작노드 저장
    need_visited.append(start_node)

    #시작을 1로 했기 때문에 나중에 최종적인 값에 -1을 해주면 된다.
    graph[start_node[0]][start_node[1]] = 1

    #break로 반복문 둘다 빠져나갈수 없기 때문에 사용하는 변수
    check  = False

    #리턴할 횟수
    result = None
    #탐색시작
    while need_visited:
        #행, 렬
        current_y, current_x = need_visited.popleft()

        for i in range(len(dx)):
            next_y = current_y + dy[i]
            next_x = current_x + dx[i]

            #목적지 노드이면 바로 출력
            if next_y == end_node[0] and next_x == end_node[1]:
                result = graph[current_y][current_x] + 1
                check = True
                break

            if next_y >= 0 and next_y < len(graph) and next_x >= 0 and next_x < len(graph[0]):
                #이동할 위치가 0이면 방문안했으니까 이동
                if graph[next_y][next_x] == 0:
                    graph[next_y][next_x] = graph[current_y][current_x]+1
                    need_visited.append((next_y,next_x))

        
        if check == True:
            break

    #시작을 1로 했기 때문에 최종적으로 -1함
    return result-1


'''입력'''
#테스트 케이스
test_case = int(sys.stdin.readline())

for _ in range(test_case):

    #체스판의 크기 - 체스판은 정사각형
    graph_size = int(sys.stdin.readline())

    #체스판 생성
    graph = [[0 for _ in range(graph_size)] for _ in range(graph_size)]

    #출발지
    start_node = tuple(map(int,sys.stdin.readline().split()))

    #도착지
    end_node = tuple(map(int,sys.stdin.readline().split()))

    if start_node == end_node:
        print(0)
        continue

    print(bfs(start_node,end_node,graph))