문제
모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다.
우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.
예를 들어, N=5이고, M=4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.
- 구슬 2번이 구슬 1번보다 무겁다.
- 구슬 4번이 구슬 3번보다 무겁다.
- 구슬 5번이 구슬 1번보다 무겁다.
- 구슬 4번이 구슬 2번보다 무겁다.
위와 같이 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다. 1번 구슬보다 무거운 것이 2, 4, 5번 구슬이고, 4번 보다 가벼운 것이 1, 2, 3번이다. 따라서 답은 2개이다.
M 개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.
입력
첫 줄은 구슬의 개수를 나타내는 정수 N(1 ≤ N ≤ 99)과 저울에 올려 본 쌍의 개수 M(1 ≤ M ≤ N(N-1)/2)이 주어진다. 그 다음 M 개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.
출력
첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력 한다.
풀이
구슬은 싸이클이 없는 단방향 그래프(Directed Acyclic Graph)로 연결되어 있다.
구슬마다 각 구슬보다 가벼운 구슬과 무거운 구슬의 개수를 탐색한다.
BFS, DFS, DP 등 다양한 방법으로 풀이할 수 있으나 DFS를 연습하기 위해 DFS로 풀이하였고 그래프는 linked list로 구현하였다.
양방향으로 탐색하기 위해 graph 배열을 2차원으로 생성하여 0번 열에는 정방향, 1번 열에는 역방향 정보를 넣어주었다.
즉, graph[i][0] : i번 구슬보다 가벼운 구슬
graph[i][1] : i번 구슬보다 무거운 구슬 의 번호가 들어있다.
재귀 함수를 통해 리프 노드에 도달할 때까지 몇 개의 자식 노드를 지나가는지 count 한다.
이 때, 방문 체크를 하면서 이미 방문한 노드는 중복 방문하지 않는다.
가벼운 구슬 혹은 무거운 구슬이 (n+1)/2개 이상이면 그 구슬은 중간이 될 수 없다.
i번 구슬의 정방향(가벼운 구슬의 개수)과 역방향(무거운 구슬의 개수)을 모두 탐색했다면 (n+1)/2이상이면 count한다.
코드
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");
const [n, m] = input[0].split(" ").map(Number);
const graph = Array.from({ length : n+1 }, () => Array.from( { length : 2 }, () => []));
// graph[i][0] : i번 구슬보다 가벼운 구슬
// graph[i][1] : i번 구슬보다 무거운 구슬
for (let i=1; i<m+1; i++) {
let [a, b] = input[i].split(" ").map(Number);
graph[a][0].push(b);
graph[b][1].push(a);
}
let visited = [];
function get_dist(cur, flag) {
if (graph[cur][flag].length === 0) return 0; // 1. 리프 노드일 때 count 시작
let dist = 0;
for (let next_node of graph[cur][flag]) { // 2. 모든 자식 노드 탐색
if (visited[next_node]) continue; // 3. 이미 방문한 노드이면 continue
visited[next_node] = true; // 4. 방문 체크
dist += get_dist(next_node, flag) + 1; // 5. next_node의 자식 노드의 개수 + 자기 자신(1)
}
return dist;
}
let cnt = 0;
for (let i=1; i<n+1; i++) {
visited = new Array(n+1).fill(false); // 방문 배열 초기화
lighter = get_dist(i, 0); // 가벼운 구슬의 개수
heavier = get_dist(i, 1); // 무거운 구슬의 개수
if (lighter >= (n+1)/2 || heavier >= (n+1)/2) cnt++;
}
console.log(cnt);