백준 풀이 - 여행 가자(1976)

가연·2025년 5월 4일

알고리즘

목록 보기

5/6

시간 복잡도(방법 1, 2 동일)

O(n^2)

방법 1 - BFS

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// "/dev/stdin"
// "test/Test.txt"
let n = Number(input[0]);
let m = Number(input[1]);

let list = [];
let trip = [];
for (let i = 2; i <= n + 2; i++) {
  if (i == n + 2) {
    trip = input[i].split(" ").map((t) => Number(t) - 1);
    continue;
  }
  list.push(input[i].split(" ").map(Number));
}

let queue = [];
let visited = new Array(n).fill(false);
queue.push(trip[0]);
visited[trip[0]] = true;
while (queue.length > 0) {
  let node = queue.shift();
  let nodeList = list[node];
  for (let i = 0; i < nodeList.length; i++) {
    if (nodeList[i] == "0") continue;
    if (visited[i] == true) continue;

    queue.push(i);
    visited[i] = true;
  }
}
let answer = true;
for (t of trip) {
  if ((visited[t] == false) | (visited[t] == undefined)) {
    answer = false;
    break;
  }
}

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

코드 설명

마지막에 나온 여행 경로가 갈 수 있는 계획인지 확인하는 문제.

마지막 경로대로 전부 확인하려면 시간초과 나올 것 같아서 bfs 로 탐색했다.

처음 계획한 리스트의 처음 노드를 시작으로 방문하지 않은 노드들을 전부 queue 에 넣어주고 연결되어있는 노드들을 전부 탐색했다.

만약 visited 에 계획된 노드들이 false 로 되어있는게 하나라도 있다면 실패한거라 NO 를 출력해줬다.

방법 2 - 유니온 파인드

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// "/dev/stdin"
// "test/Test.txt"
let n = Number(input[0]);
let m = Number(input[1]);

const parent = new Array(n + 1);
for (let i = 1; i <= n; i++) {
  parent[i] = i;
}

let graph = Array.from({ length: n + 1 }, () => Array(n + 1));

for (let i = 1; i <= n; i++) {
  let row = input[i + 1].split(" ").map(Number);
  for (let j = 1; j <= n; j++) {
    graph[i][j] = row[j - 1];
  }
}

let trip = input[n + 2].split(" ").map(Number);

function find(x) {
  if (parent[x] !== x) {
    parent[x] = find(parent[x]);
  }
  return parent[x];
}

function union(a, b) {
  let rootA = find(a);
  let rootB = find(b);
  if (rootA !== rootB) {
    parent[rootB] = rootA;
  }
}

for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
    if (graph[i][j] === 1) {
      union(i, j);
    }
  }
}

let start = find(trip[0]);
let possible = true;

for (let i = 1; i < trip.length; i++) {
  if (find(trip[i]) !== start) {
    possible = false;
    break;
  }
}

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

코드 설명

유니온파인드

상호 배타적 집합,(= 서로소 집합)
여러 노드가 있을 때, 노드들을 그룹화하고 관리하는 자료구조.

1. 부모 배열 초기화

union find 를 수행하기 위해서는 parent 배열이 필요하다.
parent 배열은 각 노드의 부모 노드를 저장하는 배열이며, 초기에는 각 노드가 자기 자신을 부모로 가진다.
```
function initParent(n) {
    const parent = new Array(n);
    for(let i = 0; i < n; i++) {
        parent[i] = i;  // 각 노드의 부모를 자기 자신으로 초기화
    }
    return parent;
}
```
2. find 함수

어떤 노드가 어느 그룹에 속하는지 알려주며, 그 그룹의 대표를 알려주는 함수.
- 만약 찾고자하는 노드 x 의 parent 가 x 와 동일하다면 그대로 return
- 동일하지 않다면 부모 노드의 대표를 찾는 함수를 실행한다.
  - 재귀적으로 올라가서 마지막 노드의 최종 대표(루트)를 찾아주게 된다.
```
function find(parent, x) {
    if(parent[x] !== x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}
```
3. union 함수

특정 노드 a,b 가 있을때 a,b 를 연결해주는 함수.
- find 를 통해 a,b 각각의 대표 노드들을 찾아준다.
- a,b 의 대표노드가 같지 않다면 b의 대표노드를 a의 대표노드 밑으로 넣어준다.
```
function union(parent, a, b) {
	let rootA = find(parent, a);
	let rootB = find(parent, b);
	if(rootA !== rootB) {
		parent[rootB] = rootA;
	}
}
```