백준 7562번 나이트의 이동
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 66648 | 35756 | 26553 | 52.472% |
문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
[입력]
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
[출력]
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
문제 해석하기
- 체스판 위에서 나이트가 주어진 시작 위치에서 목표 위치까지 최단 거리로 이동해야 한다. 이 문제는 최단 경로 탐색이기 때문에 너비 우선 탐색(BFS) 알고리즘을 사용하여 해결한다.
- BFS는 deque 모듈을 사용하므로 이를 import해주어야 한다.
- 체스판의 한 변의 길이 n을 입력으로 받아 2차원 배열 형태의 체스판을 생성한다.
- 시작 위치와 목표 위치를 각각 start_x, start_y 및 target_x, target_y로 입력받는다.
- 나이트가 이동할 수 있는 8가지 방향을 정의한다.
- BFS 함수를 작성하여 시작 위치에서부터 목표 위치까지 탐색하도록 한다.
- 방문 여부는 visited 2차원 배열을 사용하여 관리하며, 중복 방문을 방지한다.
- 이동할 때마다 이동 횟수에 +1을 해주고, 목표 위치에 도달하면 현재 이동 횟수를 반환한다.
- 테스트 케이스 수를 입력받고, 각 테스트 케이스마다 BFS 결과를 출력한다.
- 시작 위치와 목표 위치가 같다면 즉시 0을 출력한다.
from collections import deque
# 나이트가 이동할 수 있는 8가지 방향 정의
moves = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
# BFS 함수
def bfs(start_x, start_y, target_x, target_y, board_size):
# 방문 여부를 저장하는 배열
visited = [[False] * board_size for _ in range(board_size)]
queue = deque([(start_x, start_y, 0)]) # (현재 x, y, 이동 횟수)
visited[start_x][start_y] = True
while queue:
x, y, moves_count = queue.popleft()
# 목표 지점에 도달한 경우
if x == target_x and y == target_y:
return moves_count
# 나이트의 모든 이동 방향 탐색
for dx, dy in moves:
nx, ny = x + dx, y + dy
if 0 <= nx < board_size and 0 <= ny < board_size and not visited[nx][ny]:
visited[nx][ny] = True
queue.append((nx, ny, moves_count + 1))
return -1 # 도달할 수 없는 경우
t = int(input())
for _ in range(t):
n = int(input())
start_x, start_y = map(int, input().split())
target_x, target_y = map(int, input().split())
if start_x == target_x and start_y == target_y:
print(0) # 시작점과 목표점이 같은 경우
else:
print(bfs(start_x, start_y, target_x, target_y, n))
BFS 종류의 문제들
BFS(너비 우선 탐색)는 주로 그래프나 트리 구조에서 최단 경로를 찾거나, 모든 가능한 경우를 탐색하는 문제에서 사용된다.
BFS는 한 레벨씩 탐색하며 가까운 노드부터 탐색을 진행하기 때문에, 경로를 찾는 데 있어 최단 경로를 보장할 수 있다.
1. 최단 경로 탐색 문제
- 미로 찾기 문제: 출발점에서 목표점까지 최단 거리를 구할 때 사용된다. 예를 들어, 2차원 배열로 표현된 미로에서 출발지에서 도착지까지의 최단 거리를 탐색하는 문제에서 BFS는 한 레벨씩 탐색하며 가장 먼저 도달하는 경로를 보장한다.
- 지도 문제: 장애물이 있는 지형에서 시작점에서 목표점까지 가장 빠르게 갈 수 있는 경로를 찾을 때 사용된다.
2. 모든 가능한 경우 탐색
- 단어 변환 문제: 문자열의 특정 문자들을 한 번에 하나씩 변경하여 목표 문자열을 만드는 문제에서 BFS는 각 단계를 탐색하며 최단 변환 횟수를 찾을 수 있다.
- 그래프의 모든 노드 탐색: 연결된 모든 노드를 탐색하고 방문 여부를 확인할 때 BFS는 너비 우선으로 탐색하기 때문에 전체 그래프를 탐색할 때 유용하다.
3. 트리의 레벨 탐색
- 트리 구조의 탐색: 트리의 각 레벨을 탐색하여 특정 조건에 맞는 노드를 찾는 데 사용된다. 트리에서 같은 레벨의 노드를 탐색할 때 BFS는 효율적이다.
- 최단 거리 문제: 예를 들어, 루트 노드에서 특정 노드까지의 거리를 구할 때 BFS는 최적의 솔루션이다.
4. 시뮬레이션 및 퍼즐 문제
- 퍼즐 문제: 퍼즐 조각을 움직여 목표 상태로 변환하는 문제에서 BFS는 각 상태를 탐색하며 최소 이동 횟수를 찾는 데 사용된다.
- 시뮬레이션: 특정 규칙에 따라 확장 또는 전파되는 상황을 시뮬레이션할 때 BFS는 한 단계씩 전파를 시뮬레이션하기 적합하다. 예를 들어, 바이러스 확산 문제 등에서 사용된다.
오늘의 회고
bfs 문제는 보통 최단 경로 탐색 문제에서 자주 사용된다. 위에서 정리한 bfs가 자주 사용되는 문제들을 기억해뒀다가 생소한 문제가 나와도 풀 수 있도록 공부해야겠다는 생각이 들었다. dfs, bfs의 알고리즘에 대해 정확히 이해하고 넘어갈 수 있어서 좋은 시간이었다.
