| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 48001 | 24642 | 18329 | 50.226% |
문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
답안
import sys
input = sys.stdin.readline
source = [0, 0, 0] # x, y, depth
destination = [0, 0]
def get_possible_moves(visited: list[list[bool]], coordinate: tuple[int, int, int]) -> list[tuple[int, int]]:
result = []
x, y, depth = coordinate
dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [1, -1, 2, -2, 2, -2, 1, -1]
for i in range(8):
if 0 <= x + dx[i] < len(visited) and 0 <= y + dy[i] < len(visited) and \
not visited[x + dx[i]][y + dy[i]]:
result.append((x + dx[i], y + dy[i], depth+1))
return result
def dfs(visited: list[list[bool]], source: tuple[int, int, int], destination: tuple[int, int]):
stack = [source]
while stack:
x, y, depth = stack.pop(0)
if (x, y) == destination:
return depth
if not visited[x][y]:
visited[x][y] = True
stack.extend(get_possible_moves(visited, (x, y, depth)))
def solve(board_size: int) -> None:
visited = [[False for _ in range(board_size)] for _ in range(board_size)]
source = tuple(list(map(int, input().split())) + [0])
destination = tuple(map(int, input().split()))
print(dfs(visited, source, destination))
for _ in range(testcase_count := int(input())):
solve(board_size := int(input()))풀이
코드는 길지만 난이도가 아주 어렵지 않았던 문제였다.
문제를 보자마자 DFS, BFS와 같은 탐색을 하면 문제가 풀리겠다고 생각했다.
나이트가 왔다갔다 하며 제자리로 돌아오는 경우의 수를 제외한다면, 최악의 경우 최대 크기인 300 x 300 사이즈의 체스 판이라고 하더라도 90000번만 탐색한다면 나이트가 몇 번 이동하여 해당 칸으로 갔는지 파악할 수 있기 때문이다.
for _ in range(testcase_count := int(input())):
solve(board_size := int(input()))테스트케이스의 개수만큼 solve()를 반복한다.
def solve(board_size: int) -> None:
visited = [[False for _ in range(board_size)] for _ in range(board_size)]
source = tuple(list(map(int, input().split())) + [0])
destination = tuple(map(int, input().split()))
print(dfs(visited, source, destination))solve()에서는 입력을 받은 뒤, DFS를 시작한다. DFS에는 체스 보드 칸을 지난 적이 있는지를 기록한 visited, 그리고 처음 위치와 목적지 칸의 좌표를 건네준다.
def dfs(visited: list[list[bool]], source: tuple[int, int, int], destination: tuple[int, int]):
stack = [source]
while stack:
x, y, depth = stack.pop(0)
if (x, y) == destination:
return depth
if not visited[x][y]:
visited[x][y] = True
stack.extend(get_possible_moves(visited, (x, y, depth)))dfs()에서는 stack을 이용한 DFS 알고리즘을 구현하였다. 얼마나 많은 수를 둬서 나이트를 여기까지 움직이게 했는지를 기록하는 depth가 source와 coordinate의 2번째에 저장되어 있다.
((x, y, depth)의 형식)
def get_possible_moves(visited: list[list[bool]], coordinate: tuple[int, int, int]) -> list[tuple[int, int]]:
result = []
x, y, depth = coordinate
dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [1, -1, 2, -2, 2, -2, 1, -1]
for i in range(8):
if 0 <= x + dx[i] < len(visited) and 0 <= y + dy[i] < len(visited) and \
not visited[x + dx[i]][y + dy[i]]:
result.append((x + dx[i], y + dy[i], depth+1))
return resultget_possible_moves()에서는 현재 coordinate의 x, y 좌표에서부터 한 번의 이동으로 도착할 수 있는 나이트의 가능한 수들을 리턴한다.
체스 보드의 범위를 벗어난 좌표들은 제외하였고, 아직 방문하지 않은 체스 보드 칸만을 리턴했다.
여기에서 depth는 1을 더해준 채 result에 담아주었다.
def dfs(...):
...
x, y, depth = stack.pop(0)
if (x, y) == destination:
return depth
...
print(dfs(...))탐색을 하던 중 도착지 좌표에 도착하면 나이트로 얼마만큼의 수를 두었는지 기록하는 depth를 출력하면 정답으로 인정된다.
