[JavaScript] 백준 9466 텀 프로젝트 (JS)

SanE·2024년 5월 21일

Algorithm

목록 보기

107/127

텀 프로젝트

📚 문제 설명

N 명의 학생이 팀을 짜려고 한다.
각각의 학생들이 자기가 선호하는 학생을 정했을 때,
팀은 서로 선호하는 학생이 순환하도록 될 때 팀이 완성된다고 한다.

예를 들어, "1 1" 이라고 하면 1번 학생이 자기 자신을 선호하는 것이고 1번 학생 혼자 팀이 된다.
그리고 또 다른 예시로 "1 2" - "2 3" - "3 4" - "4 5" - "5 2" 라고 한다면
2 - 3 - 4 - 5 - 2 로 2 - 3 - 4 - 5가 하나의 사이클을 이루기 떄문에 팀이 된다.

👨🏻‍💻 풀이 과정

이 문제를 읽자마자 우선 DFS 문제라는 생각이 들었다.
그 후에는 아래와 같은 순서대로 로직을 구현했다.

💡 첫번쨰 제출 코드

visited를 통해 이미 방문한 부분 확인.
cnt 배열을 이용해 팀인원 체크
- 학생을 순서대로 넘어가면서 counter 증가.
- 만약 cnt 배열에 0이 아닌 수가 저장되어 있다면, 순환한 것이다.
- 따라서 counter - cnt[now] 가 팀의 인원 수.

    let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
    const TESTCASE = parseInt(input.shift());
	// 입력 인덱스를 위한 변수.
    let idx = 0;
	// 정답 출력을 위한 배열.
    let output = [];
    for (let i = 0; i < TESTCASE; i++) {
        let TestInput = parseInt(input[idx++]);
        let TestArr = input[idx++].split(' ').map(Number);
      	// 팀 인원.
        let answer = 0;
        let visited = new Array(TestInput).fill(false);
		// DFS 함수.
        const DFS = (now, counter, visited, cnt) => {
          	// 순환 체크.
            if (cnt[now] !== 0) {
                answer += counter - cnt[now];
                return;
            }
            visited[now] = true;
            cnt[now] = counter;
            const NEXT = TestArr[now] - 1;
          	// counter 증가 후, 재귀.
            DFS(NEXT, counter + 1, visited, cnt);
   		};
      
        for (let i = 0; i < visited.length; i++) {
            let cnt = new Array(TestInput).fill(0);

            if (!visited[i]) {
                DFS(i, 1, visited, cnt);
            }
        }
        output.push(TestInput - answer);
    }

    console.log(output.join('\n'));

그런데 이렇게 제출을 하면 메모리 초과가 나오게 된다.
그래서 이유를 생각해보니 cnt 배열이 호출 될 때마다 생성되기 떄문에 그런 것 같다.

예를 들어, 최악의 경우 학생 수가 최대 100,000 이기 때문에 반복문 100,000번 돌 때마다 100,000 크기의 배열이 생성되는 것이다.
그래서 cnt 배열을 밖에서 선언하고, 아래와 같이 선언한 후에 다시 제출해 보았다.

    for (let i = 0; i < visited.length; i++) {

        if (!visited[i]) {
            DFS(i, 1, visited, cnt);
            cnt.fill(0);
        }

    }

생각을 해보면 당연한 결과이다.
fill 함수의 경우 시간 복잡도가 O(n) 인데 반복문마다 들어있기 떄문에, 전체 시간 복잡도는 O(n^2)이 된다.
그렇다면, 100,000 의 제곱이 되기 때문에 당연히 시간 초과가 나는 것이다.

💡 두번쨰 제출 코드

따라서 전체적인 로직은 동일하게 구성했지만, 팀 인원 수를 구하는 부분을 수정하기로 했다.

cnt 함수 대신 finished 함수를 이용해 순환을 체크.
만약 순환이 발생했다면, 해당 위치부터 while 문을 이용해 팀의 인원수 확인.

let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const TESTCASE = parseInt(input.shift());
let idx = 0;
let output = [];

for (let i = 0; i < TESTCASE; i++) {
    let n = parseInt(input[idx++]);
    let students = input[idx++].split(' ').map(Number);
	// 인덱스 번호가 햇갈려서 1개 추가.
  	students.unshift(0);

    let visited = new Array(n + 1).fill(false);
    let finished = new Array(n + 1).fill(false);
    let result = 0;

    const DFS = (current) => {
        visited[current] = true;
        let next = students[current];

        if (!visited[next]) {
            DFS(next);
        } else if (!finished[next]) {
            // 팀일 때, 팀의 인원수를 세주는 로직.
            let temp = next;
            while (temp !== current) {
                result++;
                temp = students[temp];
            }
          	// 마지막 인원을 위해 한번 더.
            result++;
        }
		// 확인 후에 체크.
        finished[current] = true;
        console.log(finished);
    };

    for (let j = 1; j <= n; j++) {
        if (!visited[j]) {
            DFS(j);
        }
    }

    output.push(n - result);
}

console.log(output.join('\n'));