해당 포스팅은 백준 1976번 여행 가자 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.
문제
1. 문제 설명
- 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가
N개있고임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이여행 경로가 가능한 것인지 알아보자. - 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고,
A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의여행 계획이 E C B C D라면E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.
도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.
2. 입력
[첫 줄]: 도시의 수 N (N ≤ 200)[둘째 줄]:여행 계획에 속한 도시들의 수 M (M ≤ 1000)[N개의 줄]:- N개의 정수
- i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다.
[마지막 줄]: 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.
3. 출력
첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.
풀이
중간에 다른 도시를 경유해서 여행을 갈 수 있다는 말은 곧 각 여행지가 같은 트리에 있는지를 묻는다는 의미이다. 따라서 유니온 파인드로 풀 수 있는 문제이다.
마지막 줄에서 주어지는 여행계획에서 여행지[i]와 여행지[j]의 root 노드가 서로 같은 지 비교한 후 결과를 출력하면 되는 문제이다.
풀이에 사용된 로직
로직은 문제 예제를 통해 설명하겠다.
1. 초기화
첫 째 줄에 도시의 수 N이 3으로 주어졌다. 문제에서 도시 번호가 1부터 N까지 주어진다고 나와있으므로 1~3까지 3개의 노드를 만든다.
처음 3개의 노드는 무분별하게 존재한다고 가정한다. 모두 연결되지 않고 각각 자기 자신을 부모노드로 갖는다.
필자는 트리를 구현하였으며, 이를 코드로 아래와 같이 표현할 수 있다.
class Tree {
constructor(n) {
this.parent = new Array(n+1)
.fill(0)
.map((_, i) => i);
}
// union, find 함수 자리...
}
...
// 노드 N개의 트리 생성
const tree = new Tree(N);2. union, find 함수
union find 함수를 구현하였다.
union 함수: 인자로 받은 두 노드의 root 노드 중 가장 작은 노드를 root로 설정한다.find 함수: 인자로 받은 노드의 root 노드를 반환한다. 이 때 경로 압축을 통해 부모 노드를 하나로 만든다.
이를 코드로 아래와 같이 표현할 수 있다.
class Tree {
constructor(n) {
this.parent = new Array(n+1)
.fill(0)
.map((_, i) => i);
}
union(n1, n2) {
const a = this.find(n1);
const b = this.find(n2);
if (a < b) this.parent[b] = a;
else this.parent[a] = b;
}
find(node) {
if (this.parent[node] === node) {
return node;
}
this.parent[node] = this.find(this.parent[node]);
return this.parent[node];
}
}3. 도시들 경로 연결하기
예제에서 세 도시들의 경로는 아래의 인접행렬이다.
0 1 0
1 0 1
0 1 0
각 도시는 undirected이다. 1일 때 arr[i]와 arr[j]가 연결되어 있는 것이므로, 위의 행렬을 2차원 loop하면서 1일 때 union하여 연결해준다.
위의 예제의 경우 1-2, 2-1, 2-3, 3-2 간선 연결되어 있으므로 각 도시가 아래와 같이 연결될 수 있다.
같은 트리 내의 노드들은 가장 작은 노드 값을 root 노드로 하기에 1이 root 노드가 된다.
이를 코드로 아래와 같이 표현할 수 있다.
function solution() {
const [N, M] = input.splice(0, 2).flat();
const tree = new Tree(N);
const edge = input.splice(0, N);
for (let i = 1; i <= N; i++) {
for (let j = 1; j <= N; j++) {
if (edge[i-1][j-1] === 1) tree.union(i, j)
}
}
// 나머지 로직 ...
}4. 여행 계획에서 인접한 도시들이 서로 연결되었는지 확인
마지막으로 여행 계획에서 인접한 도시들이 서로 연결되어 있는지를 확인하면 된다. 이 때 연결되어 있다는 말은 같은 트리이냐는 말과 동치한다.
따라서 find 함수를 통해 두 함수의 root 노드가 같은지를 확인한다.
예제에서 각 도시들은 아래 그림과 같이 연결되어 있다.
여행 계획은 1-2-3으로 주어지는데,
1-2은 서로 연결되어 있으며2-3또한 서로 연결되어 있다.
따라서 이 여행 계획은 가능하므로 "YES"를 출력한다.
정리하자면, 여행 계획의 모든 인접한 도시들이 서로 같은 트리에 있다면 "YES", 하나라도 아닐 시엔 "NO"를 출력하면 된다.
이를 코드로 아래와 같이 표현할 수 있다.
function solution() {
const [N, M] = input.splice(0, 2).flat();
const tree = new Tree(N);
const edge = input.splice(0, N);
for (let i = 1; i <= N; i++) {
for (let j = 1; j <= N; j++) {
if (edge[i-1][j-1] === 1) tree.union(i, j)
}
}
// 여행계획에서 인접한 두 도시가 같은 트리인지 여부 확인
const path = input.flat();
let check = true;
for (let i = 1; i < M; i++) {
const n1 = tree.find(path[i-1]);
const n2 = tree.find(path[i]);
// 하나라도 같은 트리에 존재하지 않을 시 여행 불가능!
if (n1 !== n2) {
check = false;
break;
}
}
const answer = check ? "YES" : "NO";
console.log(answer)
}전체 코드
const readline = require('readline');
const input = [];
readline.createInterface({
input: process.stdin,
output: process.stdout
}).on('line', (line) => {
input.push(line.split(' ').map(elem => +elem));
}).on('close', () => {
solution();
process.exit();
});
class Tree {
constructor(n) {
this.parent = new Array(n+1)
.fill(0)
.map((_, i) => i);
}
union(n1, n2) {
const a = this.find(n1);
const b = this.find(n2);
if (a < b) this.parent[b] = a;
else this.parent[a] = b;
}
find(node) {
if (this.parent[node] === node) {
return node;
}
this.parent[node] = this.find(this.parent[node]);
return this.parent[node];
}
}
function solution() {
const [N, M] = input.splice(0, 2).flat();
const tree = new Tree(N);
const edge = input.splice(0, N);
for (let i = 1; i <= N; i++) {
for (let j = 1; j <= N; j++) {
if (edge[i-1][j-1] === 1) tree.union(i, j)
}
}
const path = input.flat();
let check = true;
for (let i = 1; i < M; i++) {
const n1 = tree.find(path[i-1]);
const n2 = tree.find(path[i]);
if (n1 !== n2) {
check = false;
break;
}
}
const answer = check ? "YES" : "NO";
console.log(answer)
}