[JavaScript/DFS] 백준 골드 3 : 9466 - 텀 프로젝트

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

---

📌 작성한 코드 

// 16920
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const T = Number(input[0]);

let visited;
let list;
let cnt = 0;
const answer = [];

const dfs = (node) => {
    visited[node] = true;
    const next = list[node];

    if (!visited[next]) dfs(next); // 다음 위치로 넘어감
    else if (!done[next]) {
        // 다음 위치 사이클 확인 한적 없음
        // 다음 위치에 방문한 적 있는데 사이클 확인한 적 없음 -> 사이클 한바퀴 돌았다는 의미
        for (let i = next; i !== node; i = list[i]) {
            cnt += 1;
        }

        cnt += 1;
    }
    done[node] = true; // node에서 시작하는 사이클 확인을 했다는 의미
};

for (let i = 1; i <= 2 * T; i += 2) {
    const N = Number(input[i]);
    list = [0, ...input[i + 1].split(" ").map((v) => Number(v))];
    visited = Array(N + 1).fill(false);
    done = Array(N + 1).fill(false);

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

    answer.push(N - cnt);
    cnt = 0;
}

console.log(answer.join("\n"));

📌 설명 

(1) dfs를 이용하여 사이클 찾기

- 재귀 dfs를 이용하여 계속해서 다음 인원으로 넘어간다. (방문하지 않은 곳인 경우)

- 다음으로 넘어가야 하는 곳이 이미 방문한 곳이라면(사이클을 확인하기 위해 이전에 방문한 적이 있는 경우) 일단 넘어가는 것을 멈춘다.

- 그리고 다음 위치에 방문한 적은 있는데 사이클을 확인한 기록이 없다면, 다음 부분에 도착하면 사이클이 만들어진다는 의미이므로 해당 위치에서 사이클 도는 동안 카운트를 세어서 팀에 포함된 학생의 수를 구해준다. done을 사용하여 사이클 확인 기록을 볼 수 있는데, 아래 필기를 보면 어떻게 적용되는지 더 잘 이해할 수 있을 것이다.

- done은 해당 node 위치에서 시작해서 사이클을 찾는 탐색이 끝났다는 의미로 찾았거나 못찾았거나 똑같이 해당 값을 true로 만들어준다. 그래서 done이 true라면 탐색이 끝났다는 의미이고, false면 현재 사이클을 탐색중이라는 의미이기 때문에 방문한 적이 있는데 done이 false면 해당 위치에서 사이클이 만들어지는 것이다.

 

(2) 모든 학생에 대해 dfs 적용하기

- 메모리 사용량을 줄이기 위해 변수를 선언해놓고, 반복할 때마다 해당 부분에 다시 N 크기의 배열을 선언하여 사용할 것이다. (최대 크기로 미리 배열을 선언하고 초기화 하며 사용했었는데 메모리 초과가 발생하였다.)

- 이미 방문한 적 있는 위치에서는 dfs를 실행하지 않고, 방문한적 없는 곳에서만 dfs를 실행하여 사이클을 찾는다.

 

* visited를 바로 업데이트 하는 이유

문제를 풀면서 가장 다루기 어려웠던 부분이 바로 visited인데, 처음에는 사이클을 돌면서 tempVisited에 이동한 위치를 저장하였다. 사이클이 만들어지면 tempVisited에 저장된 위치를 다시 visited 배열에 방문 처리하고, 사이클이 만들어지지 않으면 tempVisited에 저장된 값들을 버리는 방식으로 업데이트 해왔다. 그러나 N이 100000까지 가능한데 매번 확인하고 업데이트까지 하다보니 시간 초과가 발생하여서 해당 방법에 문제가 있다고 판단하였다.

 

그래서 다른 분의 풀이를 참고하게 되었고, 임시로 방문체크할 필요 없이 visited에 직접 방문 처리를 해도 된다는 것을 알게 되었다.

(1) 사이클이 존재하는 경우 : 가장 먼저 시작된 dfs에서 사이클을 확인하고 방문하므로, 뒷번호에서 다시 dfs 실행해서 사이클 확인할 필요 없음

(2) 사이클이 존재하지 않는 경우 : 사이클을 확인하기 위해 지나온 노드들에서 dfs를 시작해도 사이클이 안만들어진다는 의미이므로 확인할 필요 없음

📌 참고

https://velog.io/@sanbondeveloper/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%97%B0%EC%8A%B5-%EB%B0%B1%EC%A4%80-9466-%ED%85%80-%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8

[알고리즘 연습] 백준 9466 (텀 프로젝트, 자바스크립트)

 

✅ 성공