게임 보드의 승패 상태 판정

자바스크립트 코딩테스트 문제로 game-graph-retrograde 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard game-graph-retrograde 함수명: classifyGameBoardStates 제한 시간: 600ms

방향 그래프로 표현된 게임판에서 각 시작 위치가 선공 승리, 선공 패배, 무승부 중 무엇인지 판정하세요.

문제 설명

게임판에는 0번부터 n - 1번까지의 위치가 있습니다.

moves의 각 원소 [from, to]는 현재 위치가 from일 때 한 번의 턴으로 to 위치로 이동할 수 있다는 뜻입니다. 두 플레이어는 번갈아 한 번씩 이동하며, 자기 차례에 이동할 수 있는 간선이 하나도 없으면 즉시 패배합니다.

두 플레이어가 모두 최적으로 플레이한다고 할 때, 각 시작 위치의 상태를 아래 문자열 중 하나로 분류해 배열로 반환하는 classifyGameBoardStates 함수를 작성하세요.

"WIN": 현재 차례의 플레이어가 반드시 이길 수 있습니다.
"LOSE": 현재 차례의 플레이어가 어떤 선택을 해도 집니다.
"DRAW": 둘 다 패배를 강제할 수 없어 게임이 끝나지 않도록 버틸 수 있습니다.

제한사항

1 <= n <= 100000
0 <= moves.length <= 200000
각 이동은 [from, to] 형태입니다.
0 <= from, to < n
같은 방향의 이동이 중복으로 주어지지 않습니다.
자기 자신으로 돌아오는 이동 [x, x]도 있을 수 있습니다.
반환 배열의 길이는 n이어야 합니다.
반환 배열의 i번째 값은 i번 위치에서 시작했을 때의 상태입니다.
모든 시작점마다 DFS로 모든 경로를 새로 탐색하면 시간 제한을 통과하기 어렵습니다.

예시

입력: n = 5, moves = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]] -> 출력: ["WIN", "LOSE", "LOSE", "WIN", "LOSE"]
입력: n = 4, moves = [[0, 1], [1, 2], [2, 1], [2, 3]] -> 출력: ["WIN", "LOSE", "WIN", "LOSE"]
입력: n = 2, moves = [[0, 1], [1, 0]] -> 출력: ["DRAW", "DRAW"]
입력: n = 6, moves = [[0, 1], [1, 2], [2, 1], [3, 2], [3, 4], [4, 5]] -> 출력: ["DRAW", "DRAW", "DRAW", "DRAW", "WIN", "LOSE"]

힌트

이동할 수 없는 위치는 현재 플레이어가 지는 "LOSE" 상태입니다.
어떤 위치에서 상대의 "LOSE" 상태로 이동할 수 있다면, 그 위치는 "WIN"입니다.
어떤 위치의 모든 이동이 상대의 "WIN" 상태로만 향한다면, 그 위치는 "LOSE"입니다.
끝까지 승패가 확정되지 않는 위치는 순환 구조 안에서 패배를 강제할 수 없는 "DRAW"입니다.

해설

이 문제는 각 시작점에서 가능한 모든 게임 경로를 따로 탐색하면 매우 비효율적입니다. 방향 그래프에 사이클이 있으므로 단순 DFS 메모이제이션만으로도 상태 판정이 꼬일 수 있습니다.

핵심은 이미 결과가 확정된 위치에서 거꾸로 전파하는 것입니다. 먼저 각 위치의 나가는 간선 수 outDegree를 세고, 동시에 역방향 그래프 reverseGraph[to]에 from을 저장합니다.

이동할 수 없는 위치는 현재 차례의 플레이어가 바로 지므로 "LOSE"입니다. 이 위치들을 큐에 넣고 시작합니다.

큐에서 꺼낸 위치가 "LOSE"라면, 그 위치로 이동할 수 있는 이전 위치들은 상대를 패배 상태로 보낼 수 있습니다. 따라서 아직 미정인 이전 위치는 "WIN"으로 확정됩니다.

반대로 큐에서 꺼낸 위치가 "WIN"이라면, 그 위치로 이동하는 선택지는 현재 플레이어에게 좋은 선택지가 아닙니다. 이전 위치의 남은 미정 선택지 수를 하나 줄이고, 모든 이동이 "WIN" 상태로만 향한다고 확인되는 순간 그 이전 위치는 "LOSE"가 됩니다.

이 전파가 끝난 뒤에도 상태가 정해지지 않은 위치가 남을 수 있습니다. 그런 위치들은 "LOSE"로 가는 강제 경로도 없고, 모든 선택지가 "WIN"으로 막히지도 않은 순환 영역입니다. 최적 플레이에서는 패배를 피하며 게임을 계속 끌 수 있으므로 "DRAW"로 분류합니다.

각 간선은 역방향 전파 과정에서 많아야 한 번씩만 상태 계산에 사용됩니다. 따라서 전체 시간 복잡도는 O(n + moves.length), 공간 복잡도도 O(n + moves.length)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과