1976번 - 여행 가자

1️⃣ DFS

 

✏️ 풀이 과정

문제의 요구사항을 정리해보면 그래프 이론의 Connected Component를 찾으라는 것과 똑같습니다. 즉 전체 그래프에서 여행 계획에 속한 도시들이 모두 연결된 하나의 그래프 안에 있는 지를 알아내야 합니다.

 

이를 찾아내는 방법은 DFS나 BFS등의 탐색 방법을 통해서 여행 계획에 속한 하나의 도시에서 출발해서 연결된 전체 그래프를 탐색했을 때 다른 모든 도시들에 방문했는지 따져보는 것입니다.

 

경로를 신경쓸 필요가 없기 때문에 한 번의 탐색만으로 답을 찾을 수 있습니다. DFS구현에서 주의해야 할 점은 시작점을 여행 경로에 포함된 정점으로 잡고 해당 정점을 방문처리하고 시작해야 한다는 것입니다. DFS로 visited 배열에 방문 정점을 모두 표시한 이후 여행 계획과 대조해서 서모두 포함되었는 지를 체크하면 문제가 해결됩니다.    

 

⏱ 시간 복잡도

DFS의 시간 복잡도인 O(V+E)로 문제를해결할 수 있습니다. N이 200이하이고 M은 대략 200*200/2까지 가능하기 때문에 8000000 이내의 계산량으로 문제를 해결할 수 있습니다. 

 

💻 코드

JavaScript

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

const N = Number(input[0]);
const M = Number(input[1]);

const adjMatrix = Array.from(Array(N + 1), () => Array(N + 1));

for (let i = 2; i < 2 + N; i++) {
    for (let j = 0; j < N; j++) {
        adjMatrix[i - 1][j + 1] = input[i].split(" ")[j] === "1";
    }
}

const visited = [];

const dfs = (v) => {
    for (let i = 1; i <= N; i++) {
        if (adjMatrix[v][i] && !visited[i]) {
            visited[i] = true;
            dfs(i);
        }
    }
};

const plan = input[N + 2].split(" ").map(Number);
visited[plan[0]] = true;
dfs(plan[0]);

let possible = true;
for (let i = 0; i < M; i++) {
    if (!visited[plan[i]]) {
        possible = false;
        break;
    }
}

console.log(possible ? "YES" : "NO");