7. 환승(5214)
문제
아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?
입력
첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)
다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다.
출력
첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.
작성한 코드
class Queue {
constructor() {
this.items = {};
this.headIndex = 0;
this.tailIndex = 0;
}
enqueue(item) {
this.items[this.tailIndex] = item;
this.tailIndex++;
}
dequeue() {
const item = this.items[this.headIndex];
delete this.items[this.headIndex];
this.headIndex++;
return item;
}
peek() {
return this.items[this.headIndex];
}
getLength() {
return this.tailIndex - this.headIndex;
}
}
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
// n: 역의 수, k: 한 하이퍼튜브가 서로 연결하는 역의 개수, m: 하이퍼튜브 개수
let [n, k, m] = input[0].split(" ").map(Number);
// 그래프 정보(N개의 역과 M개의 하이퍼튜브는 모두 노드)
let hiperTube = [];
for (let i = 1; i <= n + m; i++) hiperTube[i] = [];
for (let i = 1; i <= m; i++) {
let arr = input[i].split(" ").map(Number);
for (let x of arr) {
hiperTube[x].push(n + i); // 노드 -> 하이퍼 튜브
hiperTube[n + i].push(x); // 하이퍼 튜브 -> 노드
}
}
let visited = new Set([1]); // 1번 노드에서 출발
let queue = new Queue();
queue.enqueue([1, 1]); // [거리, 노드 번호]
let found = false;
while (queue.getLength() != 0) {
let [dist, now] = queue.dequeue();
// N번 노드에 도착한 경우
if (now == n) {
// 절반은 하이퍼 튜브
console.log(parseInt(dist / 2) + 1);
found = true;
break;
}
// 인접 노드 하나씩 확인
for (let y of hiperTube[now]) {
// 아직 방문하지 않았다면
if (!visited.has(y)) {
queue.enqueue([dist + 1, y]); // 방문 처리
visited.add(y);
}
}
}
if (!found) console.log(-1); // N번 노드에 도달 불가능풀이
-
1번 역에서 N번 역으로 가는데 방문하는 최소 역의 수 출력
-
일종의 최단 거리 문제 → 각 간선의 비용이 모두 동일
-
하이퍼튜브를 통해서만 이동이 가능하므로, 계산된 최단 거리 값을 2로 나누면 그것이 정답
- 1 → H → 3 → H → 5 로 갔다고 하면 거리가 4이므로, 지나야 하는 역의 개수는 2개
-
문제 해결 아이디어
-
하이퍼튜브를 포함하여 전체 노드를 그래프로 구성
-
BFS를 이용해서 1번에서 N번까지의 최단 거리 계산
-
N = 5일 때의 예시
최단 경로: 1 → H → 3 → H → 5 이므로 거쳐가는 역의 수는 3
-
-
각 하이퍼튜브와 하이퍼튜브가 연결하는 노드들은 모두 양방향 간선으로 연결
8. 결혼식(5567)
문제
상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.
출력
첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.
내가 작성한 코드 → 실패
class Queue {
constructor() {
this.items = {};
this.headIndex = 0;
this.tailIndex = 0;
}
enqueue(item) {
this.items[this.tailIndex] = item;
this.tailIndex++;
}
dequeue() {
const item = this.items[this.headIndex];
delete this.items[this.headIndex];
this.headIndex++;
return item;
}
peek() {
return this.items[this.headIndex];
}
getLength() {
return this.tailIndex - this.headIndex;
}
}
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0]); // 상근이의 동기의 수(2<= n <= 500)
let m = Number(input[1]); // 친구 리스트의 길이(1<=m<=10000)
let friends = Array.from({ length: n + 1 }, () => []); // 각 친구들의 관계 담을 리스트
for (let i = 1; i <= m; i++) {
let [a, b] = input[i + 1].split(" ").map(Number);
friends[a].push(b);
}
let visited = new Array(n + 1).fill(false);
queue = new Queue();
queue.enqueue([friends[1], 1]); // 상근이의 친구 넣기
visited[1] = true;
// 상근이 친구가 없는 경우, 초대할 친구 없음
if (friends[1].length == 0) {
console.log(0);
process.exit();
}
let cnt = 0; // 초대하는 동기의 수
while (queue.getLength() != 0) {
let [friend, connect] = queue.dequeue();
if (connect > 2) break; // 친구와 친구의친구 넘었을때(친구의 친구의 친구는 안됨)
for (let x of friend) {
if (!visited[x]) {
queue.enqueue([friends[x], connect + 1]);
visited[x] = true;
cnt += 1;
}
}
}
console.log(cnt);풀이
- BFS로 구현
- connect가 2를 초과하였을 때 BFS 수행 중지
작성한 코드
class Queue {
constructor() {
this.items = {};
this.headIndex = 0;
this.tailIndex = 0;
}
enqueue(item) {
this.items[this.tailIndex] = item;
this.tailIndex++;
}
dequeue() {
const item = this.items[this.headIndex];
delete this.items[this.headIndex];
this.headIndex++;
return item;
}
peek() {
return this.items[this.headIndex];
}
getLength() {
return this.tailIndex - this.headIndex;
}
}
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0]); // 상근이의 동기의 수(2<= n <= 500)
let m = Number(input[1]); // 친구 리스트의 길이(1<=m<=10000)
let friends = Array.from({ length: n + 1 }, () => []); // 각 친구들의 관계 담을 리스트
for (let i = 1; i <= m; i++) {
let [a, b] = input[i + 1].split(" ").map(Number);
friends[a].push(b);
friends[b].push(a);
}
// 모든 친구에 대한 최단 거리 초기화
let visited = new Array(n + 1).fill(-1);
visited[1] = 0; // 시작점까지의 거리는 0으로 설정
queue = new Queue();
queue.enqueue(1); // 상근이부터
while (queue.getLength() != 0) {
let now = queue.dequeue();
// 현재 노드에서 이동할 수 있는 모든 노드 확인
for (let next of friends[now]) {
// 방문하지 않은 노드라면
if (visited[next] == -1) {
queue.enqueue(next);
visited[next] = visited[now] + 1;
}
}
}
// 최단 거리가 2 이하인 모든 친구(노드)의 수 계산
let result = 0;
for (let i = 1; i <= n; i++) {
if (visited[i] != -1 && visited[i] <= 2) {
result++;
}
}
console.log(result - 1); // 자기 자신은 제외풀이
- 그래프로 표현한 뒤에 거리가 2 이하인 노드의 수 출력
- BFS를 사용하여 각 노드까지의 최단 거리 구하기
- 즉, BFS 호출 이후 최단거리가 2 이하인 노드의 수 계산
