문제 소개
네 개의 값 n, x, y, k가 주어졌다고 가정해 봅시다. 여기서 n은 n×n 크기의 체스판을 의미하고, 좌표 (x, y)는 나이트(knight)가 놓여 있는 위치를 나타냅니다. 나이트는 정확히 k번 이동해야 하며, 매 단계마다 8가지 방향 중 하나를 균등한 확률로 무작위 선택해 움직입니다. 우리가 구해야 할 값은 k번 이동을 마친 후 나이트가 여전히 체스판 위에 남아 있을 확률(가장 가까운 정수로 반올림한 백분율)입니다. 단, 나이트가 한 번이라도 체스판을 벗어나면 다시는 판에 들어올 수 없다는 조건이 붙습니다.
핵심 아이디어
이 문제는 깊이 우선 탐색(DFS)으로 자연스럽게 해결할 수 있습니다. 핵심은 dfs(x, y, k)가 "현재 (x, y)에 있는 나이트가 앞으로 k번 이동하는 동안 체스판을 벗어나지 않을 확률"을 반환하도록 정의하는 것입니다. 8가지 이동 방향이 모두 동일한 확률(1/8)로 선택되므로, 각 하위 호출의 결과에 1/8을 곱해 모두 더하면 전체 생존 확률이 됩니다.
예제로 이해하기
예를 들어 입력이 n = 8, (x = 1, y = 1), k = 1이라면 출력은 50이 됩니다. 8×8 체스판에서 나이트의 초기 위치는 (1, 1)이며, 딱 한 번 이동할 수 있습니다. 한 번 이동했을 때 도달 가능한 8개의 위치 중 4곳만 체스판 내부에 있고, 나머지 4곳은 판 밖입니다. 따라서 확률은 50%입니다.
해결 접근 방법
- 나이트가 이동할 수 있는 8가지 방향을 리스트로 만듭니다: [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
- dfs(x, y, k) 함수를 정의합니다.
- (x, y)가 체스판 범위를 벗어나면 0을 반환합니다.
- k가 0이면(더 이상 이동할 필요가 없으면) 1을 반환합니다.
- 그렇지 않으면 8가지 이동 각각에 대해 dfs(x + dx, y + dy, k - 1) / 8 값을 구해 모두 더한 결과를 반환합니다.
- 메인 호출에서는 dfs(x, y, k) × 100을 계산한 뒤 가장 가까운 정수로 반올림하여 반환합니다.
파이썬 구현 예제
moves = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)] class Solution: def solve(self, n, x, y, k): def dfs(x, y, k): if x < 0 or y < 0 or x >= n or y >= n: return 0 if k == 0: return 1 return sum(dfs(x + dx, y + dy, k - 1) / 8 for dx, dy in moves) return round(dfs(x, y, k) * 100) ob = Solution() n = 8 x = 1 y = 1 k = 1 print(ob.solve(n, x, y, k))
입력
8, 1, 1, 1
출력
50
복잡도 분석 및 최적화 팁
위 구현의 시간 복잡도는 O(8^k)입니다. 매 단계마다 최대 8갈래로 분기되기 때문입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 O(k)입니다. k가 커지면 동일한 (x, y, k) 상태가 반복해서 계산되므로, functools.lru_cache 같은 메모이제이션을 적용하면 서로 다른 상태의 수가 최대 n×n×k개에 불과하므로 시간 복잡도를 O(n²·k)까지 크게 줄일 수 있습니다.