[백준] 2252 - 줄 세우기 (Javascript)

문제 설명 : https://www.acmicpc.net/problem/2252

 

문제 요약 :

1. 학생 두 명의 정렬 순서가 M개 주어진다.
2. 이를 토대로 올바른 정렬 순서를 만족하는 순서를 출력하라

 

문제 풀이 시간 : 1시간

문제 성공 여부 : 실패

 

 

접근 방법(실패) :

1. 그리디 하게 접근
2. A, B가 모두 없을 경우, 배열의 끝에 추가
3. A만 있을 경우, B를 A의 바로 뒤에 추가
4. B만 있을 경우, A를 B의 바로 앞에 추가
5. A, B 모두 있을 경우, 대소 비교 후 올바르면 패스, 올바르지 않을 경우 A를 B 바로 앞으로 이동

 

내가 생각한 로직의 핵심은 5번이었다.

3 3

3 5

2 3

2 5

와 같은 입력이 주어졌을 때, 5번 조건에서 대소 비교가 올바를 경우 넘어가지 않으면 다음과 같은 반례가 발생한다.

3 5 -> 3 5

2 3 -> 2 3 5

2 5 -> 3 2 5

 

따라서 이미 정렬된 2 3의 관계가 정의되어 있고, 2 5의 대소 비교가 올바를 경우 그냥 넘어가면 문제없이 줄을 세울 수 있다.

 

하지만, 3%에서 계속 오답이 나왔고 여러 반례 케이스들을 찾아보아도 찾기 쉽지 않았다.

 

반례

반례는 다음과 같다.

4 3
1 2
3 4
4 1

 

내 코드에선 다음과 같이 동작한다.

1 2 -> 1 2

3 4 -> 1 2 3 4

4 1 -> 4 1 2 3 <- 오류!

 

이처럼 A나 B를 옮겼을 때, 연쇄적으로 다른 학생들이 이동해야 하는 케이스가 발생해 버린다!

 

따라서 이 문제는 그리디 하게 해결할 수 없었다.

 

전체 코드(실패) :

const solution = () => {
  const fs = require("fs");
  const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
  const input = fs.readFileSync(filePath).toString().trim().split("\n");

  const [N, M] = input.shift().split(" ").map(Number);

  const set = new Set();

  const line = [];
  for (const compare of input) {
    const [A, B] = compare.split(" ").map(Number);
    if (!set.has(A) && !set.has(B)) {
      line.push(A);
      line.push(B);
      set.add(A);
      set.add(B);
      continue;
    }

    if (set.has(A) && set.has(B)) {
      let [a_idx, b_idx] = findIdx(line, A, B);
      if (a_idx < b_idx) continue;

      line.splice(a_idx, 1);
      line.splice(b_idx, 0, A);
      continue;
    }

    if (set.has(A)) {
      let [a_idx, b_idx] = findIdx(line, A, B);
      line.splice(a_idx + 1, 0, B);
      set.add(B);
      continue;
    }

    if (set.has(B)) {
      let [a_idx, b_idx] = findIdx(line, A, B);
      line.splice(b_idx, 0, A);
      set.add(A);
      continue;
    }
  }

  for (let i = 1; i <= N; i++) {
    if (set.has(i)) continue;
    line.push(i);
  }

  let ans = "";
  for (const a of line) {
    ans += a + " ";
  }
  return ans;
};

const findIdx = (arr, A, B) => {
  let a_idx = 0;
  let b_idx = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === A) a_idx = i;
    if (arr[i] === B) b_idx = i;
  }
  return [a_idx, b_idx];
};

const answer = solution();
console.log(answer);

 

 

 

접근 방법(성공) :

1. 위상정렬을 하자

이 문제는 위상정렬을 통해 선행되어야 하는 indegree 들을 올바르게 먼저 처리할 수 있어야 한다.

 

이를 위해, 큐나 스택을 활용할 수 있다.

 

위상 정렬을 위해 크게 두 가지 조건이 필요하다.

1. 각 노드의 indegree의 개수 저장

2. 각 노드의 indegree 노드 저장

 

1,2번 모두 M으로 주어지는 대소 비교를 토대로 구할 수 있다.

 

예를 들어 다음과 같은 입력이 있다.

4 3
1 2
3 4
4 1

 

이 경우 각각의 indegrees 배열(1)은 아래와 같다.

[x, 1, 1, 0, 1]

 

1은 4가 선행되어야 하고,

2는 1이 선행되어야 하고,

3은 선행 조건이 없고,

4는 3이 선행되어야 한다.

 

따라서 우리는 3번부터 큐에 넣고 다음 선행조건들을 찾으면 된다.

 

ans : 3

 

3을 사용했으니 3을 선행조건으로 가진 노드들의 indegree를 1씩 줄여주면 된다.

[x, 1, 1, 0, 0]

4는 3이 선행되어야 하지만, 3이 실행되었기 때문에 이제 4의 indegree는 1이 줄어 0이 된다.

 

따라서 4번을 큐에 넣고 다음 선행조건들을 계속해서 찾아주면 문제를 해결할 수 있다!

 

전체 코드(성공) :

const solution = () => {
  const fs = require("fs");
  const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
  const input = fs.readFileSync(filePath).toString().trim().split("\n");

  const [N, M] = input.shift().split(" ").map(Number);

  const indegrees = Array(N + 1).fill(0);
  const relation = Array.from({ length: N + 1 }, () => []);

  for (const line of input) {
    const [A, B] = line.split(" ").map(Number);
    relation[A].push(B);
    indegrees[B]++;
  }

  const queue = [];
  for (let i = 1; i <= N; i++) {
    if (indegrees[i] === 0) queue.push(i);
  }

  let ans = "";
  while (queue.length !== 0) {
    const cur = queue.shift();
    ans += cur + " ";
    for (const next of relation[cur]) {
      indegrees[next]--;
      if (indegrees[next] === 0) queue.push(next);
    }
  }

  return ans;
};

const answer = solution();
console.log(answer);