https://www.acmicpc.net/problem/16509
문제 이해
문제 요약
- 장기판: 10×9 크기.
- 상(相): 특정 규칙에 따라 이동할 수 있는 기물.
- 왕(왕): 궁성 내에 위치하며, 상이 왕에게 도달해야 함.
- 목표: 상이 왕에게 도달하는 최소 이동 횟수를 구하거나, 도달할 수 없으면 -1을 출력.
상의 이동 규칙
상은 8가지 방향으로 이동할 수 있습니다. 각 이동은 다음 두 단계로 이루어집니다:
- 직선 방향으로 한 칸 이동 (상, 하, 좌, 우 중 하나).
- 같은 방향의 대각선으로 두 칸 이동.
예를 들어, 상(위쪽)으로 한 칸 이동 후, 좌상향 대각선으로 두 칸 이동하는 식입니다.
추가 제약 조건
- 이동 경로에 다른 기물이 있으면 이동할 수 없음.
- 장기판을 벗어나면 이동할 수 없음.
- 왕은 항상 궁성에 위치: (0,3)-(2,5)와 (7,3)-(9,5)의 두 궁성 중 하나에 있음.
해결 방법
상은 이동할 수 있는 경로가 여러 개 있으며, 최단 이동 횟수를 찾는 문제이므로 최단 경로 알고리즘인 BFS(Breadth-First Search) 를 사용하는 것이 적합합니다. BFS는 시작점에서부터 인접한 모든 노드를 탐색한 후, 다음 레벨로 넘어가면서 최단 경로를 보장하기 때문입니다.
알고리즘 및 자료구조
사용된 알고리즘: BFS (너비 우선 탐색)
- BFS는 그래프나 트리에서 시작 노드로부터 모든 인접 노드를 탐색하고, 그 다음 레벨의 노드를 탐색하는 방식입니다.
- 장점: 최단 경로를 보장합니다.
사용된 자료구조
- 큐 (Queue): BFS에서 현재 탐색 중인 노드와 다음에 탐색할 노드를 순서대로 저장합니다. Python에서는
deque를 사용하여 효율적인 큐 구현이 가능합니다. - 방문 배열 (Visited Array): 이미 방문한 위치를 표시하여 중복 탐색을 방지합니다. 여기서는 10×9 크기의 2차원 리스트를 사용합니다.
- 이동 방향 배열 (dx, dy): 상이 이동할 수 있는 8가지 방향을 미리 정의하여, 각 방향으로의 이동을 쉽게 계산합니다.
시간 복잡도 분석
공간 복잡도
- 방문 배열: 10×9 크기의 2차원 리스트로,
O(10 * 9)=O(90)의 공간을 사용합니다. - 큐: 최악의 경우 모든 위치가 큐에 들어갈 수 있으나, 장기판의 크기가 작기 때문에 추가적인 공간은
O(90)입니다. - 기타: 이동 방향 배열 등은 고정된 크기를 가지므로 무시할 수 있습니다.
총 공간 복잡도: O(1) (상수 공간)으로 간주할 수 있습니다.
시간 복잡도
- BFS 탐색: 각 위치에서 최대 8가지 방향으로 이동을 시도합니다.
- 장기판의 전체 크기: 10×9 = 90.
- 총 연산: 각 위치당 최대 8번의 이동을 시도하므로,
O(8 * 90)=O(720)입니다. - 실제 수행 시간: 매우 작으며, 효율적인 해결이 가능합니다.
총 시간 복잡도: O(1) (상수 시간)으로 간주할 수 있습니다. 실제로는 장기판의 크기가 고정되어 있기 때문에 입력 크기에 관계없이 일정한 시간 내에 실행됩니다.
알고리즘 및 자료구조 요약
- 알고리즘: BFS를 사용하여 최단 이동 횟수를 찾습니다.
- 자료구조:
- 큐 (deque): BFS에서 탐색할 노드를 순서대로 저장.
- 방문 배열 (2D 리스트): 이미 방문한 위치를 표시하여 중복 탐색을 방지.
- 이동 방향 배열 (dx, dy): 상이 이동할 수 있는 모든 방향을 사전에 정의하여 효율적인 이동 계산.
from collections import deque
input = __import__('sys').stdin.readline
# 16509 장군
arr = [[0] * 9 for _ in range(10)]
visit = [[0] * 9 for _ in range(10)]
dx, dy = [-3, -3, -2, -2, 2, 2, 3, 3], [-2, 2, -3, 3, -3, 3, -2, 2]
r, c = map(int, input().split())
a, b = map(int, input().split())
arr[a][b] = 1
# 움직일 수 있는지 확인하는 함수
def move(i, j, tp):
tx = [
[-1, -2],
[-1, -2],
[0, -1],
[0, -1],
[0, 1],
[0, 1],
[1, 2],
[1, 2]
]
ty = [
[0, -1],
[0, 1],
[-1, -2],
[1, 2],
[-1, -2],
[1, 2],
[0, -1],
[0, 1]
]
# 상의 이동경로에 왕이 존재하면 갈 수 없음: 0 반환
for k in range(2):
x, y = i + tx[tp][k], j + ty[tp][k]
if (x == a and y == b):
return 0
return 1
def bfs(i, j):
q = deque()
visit[i][j] = 1
q.append((i, j, 0))
while q:
i, j, c = q.popleft()
for k in range(8):
x, y = i + dx[k], j + dy[k]
if not(0 <= x < 10 and 0 <= y < 9): continue
if not move(i, j, k): continue # 이동 경로에 왕이 존재하면 continue
if visit[x][y]: continue
if x == a and y == b: return c + 1
visit[x][y] = 1
q.append((x, y, c + 1))
return -1
print(bfs(r, c))