알고리즘

[백준] 7562 나이트의 이동 - 실버 1

swanzzz 2025. 3. 18. 21:57
반응형

오늘의 문제

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

 

오늘의 학습 키워드

  • BFS, Queue, 그래프이론, 그래프 탐색

 

1. 문제설명

 

 

체스판 위에 나이트가 놓여 있습니다.

나이트가 한번에 이동 가능한 칸은 위 그림처럼 초록색으로 표시되어 있습니다.

 

나이트가 이동하려고 하는 칸이 주어질 때 나이트는 몇 번 움직여야 해당 칸으로 이동할 수 있는지 구하는 문제입니다.

 

전체 테스크 케이스의 횟수가 T로 주어집니다.

체스판의 넓이 N

나이트의 현재 위치 x, y

나이트가 도착하려는 위치 x, y 가 주어집니다. 

 

제한사항

  • 시간 제한 1초
  • 메모리 제한 256MB
  • 4 <= N <= 300

2. 접근방식

전형적인 BFS를 활용하여 visited에 탐색 횟수를 기록하는 문제입니다.

 

우선 나이트의 현재 위치를 night_x, night_y로 정의해 줍니다.

그 후 도착지점을 end_x, end_y 로 설정하고 visited 배열을 생성해 줍니다.

 

visited 배열은 현재 위치를 기준으로 다음 탐색 위치로 이동했을 때 현재 위치에서 다음 위치로 이동한 횟수를 기록해 줄 것입니다.

 

따라서 N의 크기만큼 NxN 배열로 생성하고 0으로 초기화 해줍니다.

 

나머지는 문제의 코드를 직접 설명하며 구현해 보겠습니다.

 

 

3. 코드

import sys
input = sys.stdin.readline
from collections import deque

T = int(input())
for _ in range(T):
    N = int(input())
    night_x, night_y = map(int, input().split())
    end_x, end_y = map(int, input().split())
    visited = [[0] * N for _ in range(N)]

    if (night_x, night_y) == (end_x, end_y):
        print(0)
        continue

    queue = deque()
    queue.append((night_x, night_y))
    
    # 1. 나이트가 현재 위치를 기준으로 이동 가능한 경우 찾기
    dx = [-2, -1, 1, 2, 2, 1, -1, -2]
    dy = [1, 2, 2, 1, -1, -2, -2, -1]

    while queue:
        sx, sy = queue.popleft()

        for k in range(8):
            nx = sx + dx[k]
            ny = sy + dy[k]

            # 나이트가 체스판 위에 있을 때
            if 0 <= nx < N and 0 <= ny < N:
                if visited[nx][ny] == 0:
                    visited[nx][ny] = visited[sx][sy] + 1
                    queue.append((nx, ny))
    print(visited[end_x][end_y])

 

코드설명

1. 우선 입력을 받아줍니다.

import sys
input = sys.stdin.readline
from collections import deque

T = int(input())
for _ in range(T):
    N = int(input())
    night_x, night_y = map(int, input().split())
    end_x, end_y = map(int, input().split())
    visited = [[0] * N for _ in range(N)]

    if (night_x, night_y) == (end_x, end_y):
        print(0)
        continue

 

 

전체 T번 테스트 케이스가 진행되니 T 안에서 입력과 출력을 반복해 줍니다.

 

그리고 1번 예외를 바로 설정해 주었습니다.

 

 

앞선 예제를 볼 때 나이트가 1, 1에서 시작하고 1, 1에 도착하고자 할 때 현재 위치가 종료 위치라면 굳이 탐색을 시작할 이유가 없기 때문에 0을 바로 출력하도록 해주었습니다.

 

그다음 queue 자료구조를 활용해 BFS 탐색을 실시해 줍니다.

 

    queue = deque()
    queue.append((night_x, night_y))
    
    # 1. 나이트가 현재 위치를 기준으로 이동 가능한 경우 찾기
    dx = [-2, -1, 1, 2, 2, 1, -1, -2]
    dy = [1, 2, 2, 1, -1, -2, -2, -1]

    while queue:
        sx, sy = queue.popleft()

        for k in range(8):
            nx = sx + dx[k]
            ny = sy + dy[k]

            # 나이트가 체스판 위에 있을 때
            if 0 <= nx < N and 0 <= ny < N:
                if visited[nx][ny] == 0:
                    visited[nx][ny] = visited[sx][sy] + 1
                    queue.append((nx, ny))
    print(visited[end_x][end_y])

 

앞서 선언한 queue를 통해 queue를 생성해 주고 나이트의 시작 위치 night_x, night_y를 queue에 넣어줍니다.

 

그 후 나이트의 이동 가능 위치를 전부 탐색해 줄 건데 0,0을 기준으로 나이트의 이동위치를 계산하면 다음과 같습니다.

 

이를 그대로 dx와 dy로 설정해 작성해 주었습니다.

 

이제 무한 반복하며 queue에 저장된 나이트의 시작값을 꺼내어 visited 배열을 채워줄 것입니다.

 

queue에 더 이상 값이 없는데도 반복을 진행하면 안 되니 while 문의 조건을 queue의 여부를 넣어준 것입니다.

 

queue.popleft()를 통해 가장 먼저 들어온 값을 꺼내어 주고 해당 위치를 기준으로 8번 탐색을 실시하며 다음 위치를 계산해 queue에 넣어줄 것입니다.

 

이때 queue에 들어갈 때 체스판의 범위를 벗어나지 않고 이전에 방문하지 않은 곳을 넣어주어야 합니다. 

 

따라서 조건을 위 조건처럼 작성해 주었고 visited 배열은 누적값을 기록하기 위해 이전값에 +1 하는 방식으로 기록해 주었습니다.

 

모든 조건을 만족하는 다음 위치를 queue에 넣어주고 while 문을 계속 돌려줍니다.

 

모든 탐색이 종료되었을 때 visited 배열의 도착 위치를 출력하면 나이트가 몇 번 만에 해당 위치에 도착하였는지 알 수 있습니다.

 

 

4. 결과

 

 

회고

이전 항해 99 코드 챌린지를 참여하며 골드 1 수준의 알고리즘 문제를 해결했었는데 오랜 기간 동안 알고리즘을 풀지 않아 많이 까먹은 상태였습니다.

 

감을 되살리고 문제 해결 능력을 키우기 위해 최근부터 알고리즘 1일 1문제를 해결하기 위해 기록하고 있습니다.

 

이 문제는 BFS 감을 잡기 위한 문제로 생각보다 쉬웠고 이전에 풀었던 기억이 떠올라서 해결이 가능했습니다.

 

앞으로 꾸준히 문제를 해결하며 그 그 결과를 기록해 보겠습니다.

반응형