[백준] 17204 - 죽음의 게임

문제 링크 : https://www.acmicpc.net/problem/17204

문제 탐색하기

1) 문제 분석

N : 사람 수, K : 보성이 번호
줄마다 지목하고자 하는 사람의 수 (origin -> next)
게임 시작하는 사람은 0번
보성이가 벌주를 마시기 위해 영기가 불러야 하는 작은 양의 정수 M을 찾기.
방법이 없으면, -1을 출력

2) 가능한 시간복잡도

(1) 입력 처리 -> O(N)

첫 줄 입력 -> O(1)
N줄 입력 -> O(N)
O(1) + O(N) = O(N)

(2) 선택지 배열, 방문여부 배열 생성 -> O(N)

O(N) + O(N) = O(N)

(3) 지목 따라가며 탐색 -> O(N)

(4) 결과 출력 -> O(1)

(5) 전체 시간복잡도

입력 처리 : O(N)
배열 생성 : O(N)
지목 탐색 : O(N)
결과 출력 : O(1)-> 총합 : O(N)

3) 알고리즘 선택 이유

이 문제는 0번부터 시작하여 지목을 따라가면서 보성을 찾는지를 확인하는 간단한 단일 경로 탐색 문제이다. 각 사람이 최대 1번만 방문되므로, 사이클을 형성하지 않는 한 순차적으로 따라가기만 하면 되는 구조이다. 따라서 방문 체크를 활용한 단순 탐색 알고리즘이 가장 효율적이다.
구체적으로:
- 입력으로 주어진 지목 정보를 배열에 저장하고,
- 0번부터 시작해 지목된 사람을 따라가며,
- 방문 여부를 기록하면서 보성을 찾으면 그 시점의 카운트를 출력한다.
완전탐색, DFS, BFS 등의 복잡한 방법은 불필요하고, 지목을 따라가는 단순한 선형 탐색으로 충분히 해결할 수 있다.
-> 따라서 O(N) 복잡도의 선형 순회 알고리즘을 선택하는 것이 최적이다.

코드 설계하기

1. 실행 구조

1) 입력 받기

총 인원, 보성이 숫자
지목 내용

2) 배열 생성

선택지
방문 여부

3) 지목 따라가며 탐색

현재 보성이면 탐색 종료
그렇지 않으면, 방문 체크 / 외침 횟수 증가 / 지목된 사람으로 변경

4) 결과 출력

2. 고민이 되었던 부분

: 영기가 몇 번째 외침에서 보성이 벌칙을 받게 될지를 찾기 위해, 어떤 로직으로 지목 순서를 추적해야 할지 먼저 고민하게 되었다. 보성이 등장하는 시점의 순서를 빠르고 정확하게 판별할 수 있는 구조를 만드는 것이 핵심 과제였다. 이를 해결하기 위해 두 가지 전제를 세웠다.

첫 번째, 각 사람이 지목한 대상을 빠르게 찾을 수 있도록 선택지 배열을 그대로 사용하고, 방문한 사람을 기록할 수 있는 방문여부 배열을 선언했다. 이를 통해 이미 방문한 사람을 다시 방문하지 않도록 차단하고, 사이클에 갇히는 경우를 빠르게 감지할 수 있도록 설계했다.

두 번째, 0번부터 지목을 따라가며 순서를 카운트하다가, 지목된 사람이 보성이 되는 순간 즉시 해당 카운트를 출력하도록 구성했다. 보성을 만나지 못하고 사이클이 발생한 경우에는 바로 -1을 출력하여 게임이 종료되지 않는 경우도 처리할 수 있도록 설계했다.

이렇게 함으로써, 지목을 따라가는 선형 순회 방식으로 보성을 찾는 최적의 구조를 완성할 수 있었고, 복잡한 알고리즘 없이도 효율적으로 문제를 해결할 수 있었다.

정답 코드

JavaScript

// 사용 언어 : Javascript

// 입력 데이터 읽기 및 전처리
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

// 인원수(N)와 보성이 번호(K) 추출
const [memberCount, boseong] = input[0].split(" ").map(Number);

// 첫 번째 줄(조건) 제거 후 선택지 배열 생성
input.shift();
const choiceArr = [];
input.forEach(choice => choiceArr.push(Number(choice)));

// 방문 여부를 체크할 배열 (N명)
const visited = new Array(memberCount).fill(false);

// 변수 초기화
let current = 0;                    // 0번 부터 시작
let isBoseong = false;              // 보성을 만났는지 여부
let count = 0;                      // 외쳐야 하는 숫자 (최종 M)

// 지목을 따라가며 탐색
while (!visited[current]) {

    // 현재 지목된 사람이 보성인 경우
    if (current === boseong) {
        isBoseong = true;
        break;
    }

    // 아직 보성을 만나지 못한 경우
    visited[current] = true;        // 현재 사람 방문 체크
    count++;                        // 외친 횟수 증가
    current = choiceArr[current];   // 다음 지목된 사람으로 이동
}

// 결과 출력
if (isBoseong) {
    console.log(count);             // 보성이가 벌칙을 받게 되는 M 출력
} else {
    console.log(-1);                // 끝까지 가도 보성을 못 만나면 -1 출력
}

마무리하며

이 문제의 핵심은 보성을 만나야 하는 조건이 문제 해결의 핵심이었다. 보성이 벌칙을 받는다는 조건이 단순히 탐색 중간에 보성을 찾는 것과는 다르다는 점, 그리고 이를 위해 지목 순서를 정확히 추적해야 한다는 점이 생각보다 중요한 부분이었다.

이번 문제를 풀면서 문제의 본질을 먼저 파악하는 것이 얼마나 중요한지 다시금 느꼈다. 단순히 지목을 따라가면 되는 문제라 생각했지만, 방문한 사람을 관리하지 않으면 사이클에 빠질 수 있고, 보성을 만나는 시점과 게임이 끝나는 시점을 구분하지 않으면 틀릴 수 있다는 사실을 경험을 통해 깨닫게 되었다.

개인적으로 이번 문제는 단순 구현처럼 보이지만, 실제로는 문제의 상황을 코드로 정확히 해석하고, 조건을 충족하는 타이밍을 올바르게 판단하는 과정이 더 중요했다. 단순히 정답을 맞추는 것을 넘어서, 문제를 정확히 이해하고 그 구조를 코드로 옮기는 과정 자체가 문제 해결력이라는 점을 다시 한 번 실감하게 되었다. 또한, 앞으로도 빠르게 문제를 푸는 것에 집중하기보다는, 문제를 정확히 이해하고 내 코드가 정말 문제를 올바르게 해결하고 있는지 스스로 검증하는 개발자가 되고 싶다는 다짐을 하게 된 문제였다.

최근 글