[C4] 11725 - 트리의 부모찾기

문제

 

풀이

보통은 트리 구조를 만들거나, 자식 트리를 찾는 문제가 많은데 이번에는 부모 트리를 찾는 문제가 나왔다.

나는 최상위 노드부터 한단계씩 아래로 내려가는 방법을 사용하기 위해  bfs를 이용했다.

각 노드별로 탐색하며, 현재 탐색하는 노드에 자식 노드가 있다면, 그 자식 노드의 부모 노드로 현재 노드를 추가해주는 방법을 사용하기로 했다.

 

먼저 그래프 구조를 만들어 준다.

const graph = {};
input.forEach(([s, e]) => {
  if (!graph[s]) graph[s] = [];
  if (!graph[e]) graph[e] = [];

  graph[s].push(e);
  graph[e].push(s);
});

 

그래프 구조를 만들면, 한 노드에 연결된 노드들이 어떤 것이 있는지 알 수 있다.

 

 

한 노드를 방문했다면, 그 노드를 다시 방문하지 않도록 방문 처리를 해줘야 한다.

그렇기 위해서 방문 여부를 체크할 check 배열을 만들어준다.

그 다음, 각 노드의 부모 요소를 체크하기 위한 parents 객체를 만들어주면 준비 끝.

 

bfs는 큐를 이용해 구현하기 때문에, 큐에는 맨 처음 노드인 1번 노드를 넣어준다.

 const check = Array(n + 1).fill(false);
const queue = [1];

const parents = {};

 

그 다음, bfs를 통해 1번 노드부터 탐색을 시작해 주자.

여타 진행사항은 bfs와 같다.

현재 노드를 꺼내고, 현재 노드와 연결된 노드들의 방문 여부를 체크한다.

만약 방문 한 적 없다면, 다음 노드를 방문처리 한 후 큐에 넣어주면 된다.

이때, '방문 한 적 없는 다음 노드'는 현재 노드에 연결되어 있는 자식 노드가 된다.

따라서, '방문한 적 없는 다음 노드'의 부모 노드를 현재 노드로 설정해 주기만 하면 된다.

 

while (queue.length > 0) {
  const cur = queue.shift();
  check[cur] = true;

  for (next of graph[cur]) {
    if (!check[next]) {
      queue.push(next);
      parents[next] = cur;
      check[next] = true;
    }
  }
}

 

코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = []

rl.on('line', (line) => {
  input.push(line.split(' ').map(Number))
}).on('close', () => {
  const [n] = input.shift();

const graph = {};
input.forEach(([s, e]) => {
  if (!graph[s]) graph[s] = [];
  if (!graph[e]) graph[e] = [];

  graph[s].push(e);
  graph[e].push(s);
});

const check = Array(n + 1).fill(false);
const queue = [1];

const parents = {};
while (queue.length > 0) {
  const cur = queue.shift();
  check[cur] = true;

  for (next of graph[cur]) {
    if (!check[next]) {
      queue.push(next);
      parents[next] = cur;
      check[next] = true;
    }
  }
}

console.log(Object.values(parents).join("\n"));
  process.exit(0);
});