소셜 네트워킹 어플리케이션
📚 문제 설명
N 명의 친구와 친구 관계가 나와있는 k가 주어졌을 때,
입력으로 주어진 두 친구가 서로 연결될 수 있는지 찾는 프로그램을 만들어라.
예를 들어 "a b"라는 입력이 들어왔으면 a와 b가 연결될 수 있다면 1을 출력, 연결 될 수 없다면 0을 출력하면 된다.
👨🏻💻 풀이 과정
각각의 친구가 연결이 되어 있는지 찾는 문제이다.
예를 들어 트리 구조라고 생각하면,
트리 최상단의 부모 노드를 찾아서 두 친구의 부모 노드가 같다면 연결되어 있다고 생각할 수 있을 것이다.
이렇게 부모 찾기를 하는 경우 Union - Find 알고리즘을 이용하면 된다.
💡1차 제출 코드 (Fail)
Union - Find 알고리즘은 간단하게 말해서 아래 두 함수를 이용하면 된다.
Find() : 부모를 찾는 함수.
Union : 두 부모가 같으면 같은 값으로 변경하는 함수.
그럼 이제 전체 로직에 대해 설명하면 아래와 같다.
- 재귀를 이용해
Find()구현. Find()함수를 이용해Union()구현.- 각각의 테스트 케이스마다 아래 과정 반복.
- 연결 관계를 보고
Union()진행. - 출력을 원하는 친구 관계를 보고 결과 배열에 push.
- 연결 관계를 보고
- 결과 배열을 보고 결과 출력.
전체 코드
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
let TestCase = parseInt(input.shift());
// Find
const Find = (child, map) => {
if (map[child] === child) return child;
map[child] = Find(map[child], map);
return map[child];
};
// Union
const Union = (line, map) => {
const [ChildA, ChildB] = line;
const AFather = Find(ChildA, map);
const BFather = Find(ChildB, map);
if (AFather < BFather) {
map[BFather] = AFather;
} else if (AFather > BFather) {
map[AFather] = BFather;
}
};
// 반복문을 위한 index 번호.
let idx = 0;
// 테스트 케이스 번호.
let SceneNum = 1;
// 정답 문자열.
let string = '';
// 테스트 케이스 진행.
while (input.length > idx) {
// 입력 받는 부분.
let N = parseInt(input[idx++]);
let M = parseInt(input[idx++]);
let lines = input.splice(idx, M).map(v => v.split(' ').map(Number));
let A = parseInt(input[idx++]);
let answer = input.splice(idx, A).map(v => v.split(' ').map(Number));
// 부모를 저장할 배열.
// 초기값은 자기 자신으로 초기화.
let Map = Array.from({length: N}, (value, index) => index);
// 연결 관계를 보고 Union 진행.
for (const line of lines) {
Union(line, Map);
}
// 출력 문자열 배열.
let output = [`Scenario ${SceneNum}:`];
// 출력을 원하는 관계.
for (const INPUT of answer) {
const [Start, End] = INPUT;
// 만약 두 노드의 부모가 같다면.
if (Map[Start] === Map[End]) {
output.push(1);
} else {
output.push(0);
}
}
SceneNum++;
string += output.join('\n');
// 정답 형식을 맞추기 위해.
string += '\n\n';
}
console.log(string.trim());
💡2차 제출 코드
위의 과정에서 어느 부분이 잘못되었을까?
바로 위의 코드가 작동하지 않는 반례에 대해 설명하겠다.
예를들어
for (const INPUT of answer) {
const [Start, End] = INPUT;
// 만약 두 노드의 부모가 같다면.
if (Map[Start] === Map[End]) {
output.push(1);
} else {
output.push(0);
}
}테스트 케이스 진행 과정에서 위의 과정이 어느 정도 진행되어 Map 배열이 아래와 같이 되었다고 생각해보자.
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 4 | 4 | 4 |
그리고 마지막에 [1, 4] 라는 값을 받으면 아래와 같이 바뀌게 된다.
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 4 | 4 |
이렇게 된 후에 만약 [1, 5]의 관계를 묻게 된다면,
1 !== 4 이기 때문에 0이 출력되게 되며 이게 바로 위의 코드가 틀린 이유이다.
결국 누군가의 부모 노드가 마지막에 바뀌면 해당 값이 전부 바뀌지 않기 때문에 발생한 문제이다.
그럼 해결 방법은 아주 간단하다.
for (const INPUT of answer) {
const [Start, End] = INPUT;
if (Find(Start, Map) === Find(End, Map)) {
output.push(1);
} else {
output.push(0);
}
}위의 코드처럼 각각의 노드의 부모 노드를 확인하고 결과를 출력하면 될 것이다.
전체 코드
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
let TestCase = parseInt(input.shift());
// Find
const Find = (child, map) => {
if (map[child] === child) return child;
map[child] = Find(map[child], map);
return map[child];
};
// Union
const Union = (line, map) => {
const [ChildA, ChildB] = line;
const AFather = Find(ChildA, map);
const BFather = Find(ChildB, map);
if (AFather < BFather) {
map[BFather] = AFather;
} else if (AFather > BFather) {
map[AFather] = BFather;
}
};
// 반복문을 위한 index 번호.
let idx = 0;
// 테스트 케이스 번호.
let SceneNum = 1;
// 정답 문자열.
let string = '';
// 테스트 케이스 진행.
while (input.length > idx) {
// 입력 받는 부분.
let N = parseInt(input[idx++]);
let M = parseInt(input[idx++]);
let lines = input.splice(idx, M).map(v => v.split(' ').map(Number));
let A = parseInt(input[idx++]);
let answer = input.splice(idx, A).map(v => v.split(' ').map(Number));
// 부모를 저장할 배열.
// 초기값은 자기 자신으로 초기화.
let Map = Array.from({length: N}, (value, index) => index);
// 연결 관계를 보고 Union 진행.
for (const line of lines) {
Union(line, Map);
}
// 출력 문자열 배열.
let output = [`Scenario ${SceneNum}:`];
// 출력을 원하는 관계.
for (const INPUT of answer) {
const [Start, End] = INPUT;
// 각각의 부모를 찾아서 비교.
if (Find(Start, Map) === Find(End, Map)) {
output.push(1);
} else {
output.push(0);
}
}
SceneNum++;
string += output.join('\n');
// 정답 형식을 맞추기 위해.
string += '\n\n';
}
console.log(string.trim());🧐 후기
Union-Find 문제를 전에도 풀어본적이 있긴하지만, 아직 Union-Find 문제가 익숙하지 않은 것인지 Union와 Find 함수를 구현하는데 생각보다 오랜 시간이 걸렸다.
그리고 이 문제의 경우 출력이 조금 독특한데, 각각의 테스트 케이스 사이에 줄변경이 반드시 있어야 한다. 궁금해서 한번 줄을 한칸 띄우지 않았더니 바로 출력 형식 에러가 났다.
