DFS 문제풀이(2)

3. 노드 사이의 거리(1240)

문제
N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N과 거리를 알고 싶은 노드 쌍의 개수 M이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

작성한 코드

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

let [n, m] = input[0].split(" ").map(Number); // n: 노드의 개수, m: 거리를 알고 싶은 노드 쌍의 개수

let graph = Array.from({ length: n + 1 }, () => []); // 인접 리스트
for (let i = 1; i <= n; i++) {
  let [a, b, cost] = input[i].split(" ").map(Number);
  graph[a].push([b, cost]);
  graph[b].push([a, cost]);
}

// dfs 메서드 정의
function dfs(x, cost) {
  if (visited[x]) return; // 각 노드 한번씩만 방문
  visited[x] = true;
  distance[x] = cost;
  for (let [y, c] of graph[x]) dfs(y, c + cost);
}

for (let i = 0; i < m; i++) {
  let [a, b] = input[n + i].split(" ").map(Number);
  visited = new Array(n + 1).fill(false); // 방문 여부
  distance = new Array(n + 1).fill(-1); // 시작점부터 거리 계산
  dfs(a, 0); // a부터 출발했을 때 모든 노드까지의 거리 계산
  console.log(distance[b]); // y까지의 최단 거리
}

풀이

• 트리가 양방향 간선으로 구성 → 간선의 개수: N-1개
• 트리에서 노드 A와 B를 잇는 경로는 오직 1개만 존재 → 노드 사이의 거리 시간복잡도: O(N)
• 트리에서는 BFS가 아닌 DFS로도 간단히 최단 거리 계산 가능
• 단순히 매 쿼리마다 노드 A에서 B까지의 거리 계산

---

4. 단지번호붙이기(2667)

문제
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

작성한 코드

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

let n = Number(input[0]); // 지도의 크기 N
let maps = Array.from({ length: n }, () => []);
for (let i = 0; i < n; i++) {
  maps[i] = input[i + 1].split("").map(Number);
}

let answer = []; // 각 단지 내 집의 수 담을 배열
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    let count = dfs(i, j);
    if (count > 0) answer.push(count);
  }
}

function dfs(x, y) {
  if (x < 0 || x >= n || y < 0 || y >= n) return 0;
  if (maps[x][y] === 1) {
    maps[x][y] = -1; // 방문 표시
    let cnt = 1; // 단지 내 집의 수 카운트
    // 상하좌우로 이동하며 dfs 함수 호출
    cnt += dfs(x + 1, y);
    cnt += dfs(x - 1, y);
    cnt += dfs(x, y + 1);
    cnt += dfs(x, y - 1);
    return cnt;
  }
  return 0;
}

answer.sort((a, b) => a - b);
console.log(answer.length + "\n" + answer.join("\n"));

풀이

• 연결요소: 모든 두 꼭짓점 사이에 경로가 존재하는 그래프
• 각 연결 요소에 포함된 원소의 개수를 계산하는 것
• 연결 요소의 개수를 세는 방법
  1. 방문하지 않은 노드를 만날 때마다 카운트하고, DFS를 호출
  2. DFS는 해당 위치로부터 연결된(연결요소에 포함된) 모든 노드를 방문 처리