sungyup's.

algorithm_programmers / 자료구조 / 4.2 그래프, DFS/BFS

4.2그래프, DFS/BFS

프로그래머스 동적계획법 문제 정리

개요

프로그래머스에는 자료구조/알고리즘 유형별로 정리해둔 문제집인 코딩테스트 고득점 Kit이 있다. 이 중 그래프, DFS/BFS 관련 5문제를 풀어본다.

1. 가장 먼 노드(Lv.3)

가장 먼 노드는 n개의 노드가 있는 그래프에서, 간선(edge)에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 반환하는 함수를 작성하는 문제다. 여기서, 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드다.

다른 노드들까지의 "최단 거리"를 찾는 것이므로 BFS 문제다. BFS는 층층이 퍼지듯이 탐색하기 때문에 최단 거리를 보장하지만, DFS는 경로는 찾지만 먼저 깊이 들어가는 방식이라 최단 경로를 보장하지 못하고, 더 긴 경로를 먼저 탐색할 수도 있기 때문이다.

양방향 그래프 인접 목록을 생성하고, BFS로 1번 노드에서 다른 노드로의 최단 거리를 구한다. 이후, 가장 먼 거리의 값을 찾고 그 거리를 가진 노드의 개수를 반환한다.

javascript
function solution(n, edge) {
    const graph = Array.from({length: n + 1}, () => []);
    const visited = Array(n + 1).fill(false);
    const distance = Array(n + 1).fill(0);
    
    for(const [a, b] of edge){
        graph[a].push(b);
        graph[b].push(a);
    }
    
    const queue = [1];
    visited[1] = true;
    
    while(queue.length){
        const current = queue.shift();
        
        for(const next of graph[current]){
            if(!visited[next]){
                visited[next] = true;
                distance[next] = distance[current] + 1;
                queue.push(next);
            }
        }
    }
    const maxDistance = Math.max(...distance);
    return distance.filter(d => d === maxDistance).length;
}

2. 순위(Lv.3)

순위는 권투 선수의 수 n과 경기 결과를 담은 2차원 배열 results가 매개 변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 반환하는 함수를 작성하는 문제다. 경기 결과에는 모순이 없기 때문에, 예를 들어 5명이 주어졌을 때 한 선수가 4위인 선수에게 패했으면 그 선수는 다른 모든 선수에게도 패하는 5위 선수이다.

그래프의 용어로 번역하면, 이 문제는 각 선수 간의 승패 기록으로 누가 누구를 이겼는지, 즉 방향이 있는 유향 그래프를 만들고 이를 기반으로 이긴 사람/진 사람을 전부 알아낼 수 있는 사람이 있다면 순위를 정확히 판단할 수 있는 사람이다. 순위를 정확히 판단할 수 있으려면 이긴 사람 + 진 사람의 총합이 n - 1인 사람이 있다면 그 사람은 순위를 확정할 수 있는 사람이다.

확인을 위해 각 선수(노드)에 대해 그 선수가 이긴 사람들과 그 선수에게 이긴 사람들을 DFS로 탐색하고, 수를 합산해서 n - 1인지 확인한다.

javascript
function solution(n, results) {
    const winGraph = Array.from({ length: n + 1 }, () => []);
    const loseGraph = Array.from({ length: n + 1 }, () => []);

    for (const [winner, loser] of results) {
        winGraph[winner].push(loser); // winner -> loser
        loseGraph[loser].push(winner); // loser <- winner
    }

    function dfs(start, graph, visited) {
        for (const next of graph[start]) {
            if (!visited[next]) {
                visited[next] = true;
                dfs(next, graph, visited);
            }
        }
    }

    let count = 0;
    for (let i = 1; i <= n; i++) {
        const visitedWin = Array(n + 1).fill(false);
        const visitedLose = Array(n + 1).fill(false);
        dfs(i, winGraph, visitedWin);  // 해당 선수가 이긴 사람
        dfs(i, loseGraph, visitedLose); // 해당 선수를 이긴 사람

        const known = visitedWin.filter(v => v).length + visitedLose.filter(v => v).length;
        if (known === n - 1) count++;
    }

    return count;
}

이 문제는 BFS로도 풀 수 있다. dfs 함수 대신 bfs를 만들어 쓰면 된다.

javascript
function solution(n, results) {
    const winGraph = Array.from({ length: n + 1 }, () => []);
    const loseGraph = Array.from({ length: n + 1 }, () => []);

    for (const [winner, loser] of results) {
        winGraph[winner].push(loser);
        loseGraph[loser].push(winner);
    }

    function bfs(start, graph) {
        const visited = Array(n + 1).fill(false);
        const queue = [start];
        visited[start] = true;
        let count = 0;

        while (queue.length > 0) {
            const current = queue.shift();
            for (const next of graph[current]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.push(next);
                    count++;
                }
            }
        }

        return count;
    }

    let answer = 0;
    for (let i = 1; i <= n; i++) {
        const winCount = bfs(i, winGraph);  // 해당 선수가 이긴 사람 수
        const loseCount = bfs(i, loseGraph); // 해당 선수가 진 사람 수
        if (winCount + loseCount === n - 1) answer++;
    }

    return answer;
}

DFS, BFS 외에도 이 문제는 플로이드 와샬 방식(Floyd-Warshall)이라는 방법으로도 풀 수 있다. 이 방법은 모든 선수 간의 승패를 기록하는데, graph[i][j]는 i가 j를 이겼으면 true를 저장한다. 또, i가 j를 이겼고 j가 k를 이겼으면 i는 k를 이겼다는 것을 전제로 한다.

javascript
function solution(n, results) {
    const graph = Array.from({ length: n + 1 }, () => Array(n + 1).fill(false));

    for (const [a, b] of results) {
        graph[a][b] = true;
    }

    // 플로이드 와샬
    for (let k = 1; k <= n; k++) {
        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= n; j++) {
                if (graph[i][k] && graph[k][j]) {
                    graph[i][j] = true;
                }
            }
        }
    }

    let answer = 0;
    for (let i = 1; i <= n; i++) {
        let count = 0;
        for (let j = 1; j <= n; j++) {
            if (i === j) continue;
            if (graph[i][j] || graph[j][i]) count++;
        }
        if (count === n - 1) answer++;
    }

    return answer;
}

DFS와 BFS는 O(n ^ 2)의 시간복잡도를 가지는데 비해 플로이드 와샬은 3중 for문으로 시간복잡도가 O(n ^ 3)이다. 이는 모든 경로를 탐색하기 때문이며, 시간 복잡도가 아주 높지만 작은 n일때는 안정적이다.

3. 네트워크(Lv.3)

네트워크는 DFS/BFS 카테고리에 있는 그래프 문제로, 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 주어지면 네트워크의 개수(서로 연결되지 않고 별도로 존재하는 네트워크 수)를 구하라는 문제다.

여기서 주어진 computers는 인접 행렬(Adjacency Matrix)다. 예를 들어, n이 3일때 computers가 [[1, 1, 0], [1, 1, 0], [0, 0, 1]]라면 0번째, 1번째 컴퓨터는 연결된 것이고([0][1]과 [1][0] 모두 1이니) 2번째 컴퓨터는 독립 네트워크다.

이 문제는 하나의 시작 노드(정점)로부터 연결된 노드들을 모두 탐색하고 visited 배열 또는 객체에 저장해둔 후 카운터를 올리고, 다른 노드들로부터 시작하며 visited 배열에 있다면 스킵, 없다면 연결된 노드들을 탐색하고 또 카운터를 올리는 식으로 풀 수 있다. DFS와 BFS 모두 문제를 해결할 수 있다. 방문하지 않은 노드를 기준으로 해당 노드와 연결된 네트워크 전체를 순회하고, 순회 중인 노드와 연결된 노드는 모두 방문한 것으로 처리하는 식으로 네트워크 하나 하나를 카운트한다.

3-1. 네트워크(DFS)

DFS는 재귀로 해결한다. 모두 false로 채운 visited 배열을 하나 두고, 0번째 ~ n번째 노드를 순회하며 각 노드와 연결된 노드에 해당하는 visited의 인덱스에는 true를 할당하고, visited가 false인 노드를 시작 노드로 받으면 카운터를 올리고 dfs 함수를 그 노드로부터 시작하며 또 visited를 체크하면 된다.

javascript
function solution(n, computers){
  const visited = new Array(n).fill(false);
  let count = 0;

  function dfs(node){
    visited[node] = true;

    for(let i = 0; i < n; i++){
      if(!visited[i] && computers[node][i] === 1){
        dfs(i);
      }
    }
  }

  for(let i = 0; i < n; i++){
    if(!visited[i]){
      dfs(i);
      count++;
    }
  }
  return count;
}

3-2. 네트워크(BFS)

BFS도 DFS와 같은 방식으로, visited 배열에 false를 채우고 0번째 ~ n번째 노드까지 순차적으로 순회하며 해당 노드와 연결된 노드들을 탐색하며 true를 할당한다. false인 노드로부터 시작하게 되면 카운터를 올리고 해당 노드로부터 bfs를 시행한다.

javascript
function solution(n, computers) {
    const visited = new Array(n).fill(false);
    let count = 0;

    function bfs(start) {
        const queue = [start];
        visited[start] = true;

        while (queue.length) {
            const node = queue.shift();

            for (let i = 0; i < n; i++) {
                if (computers[node][i] === 1 && !visited[i]) {
                    visited[i] = true;
                    queue.push(i);
                }
            }
        }
    }

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            bfs(i);
            count++;
        }
    }

    return count;
}

4. 게임 맵 최단거리(Lv.2)

게임 맵 최단거리는 최단 거리를 구하는 문제이므로 BFS가 적절하다.

맵을 그래프로 보고, 시작점 (0, 0)에서 도착점 (n-1, m-1)까지의 최단 거리를 구하면 된다.

javascript
function solution(maps){
  const n = maps.length;
  const m = maps[0].length;

  const visited = Array.from({length: n}, () => Array(m).fill(false));
  const queue = [[0, 0, 1]]; // [x, y, 거리]
  visited[0][0] = true;

  const dx = [-1, 1, 0, 0]; // 상하좌우
  const dy = [0, 0, -1, 1];

  while(queue.length){
    const [x, y, dist] = queue.shift();

    if(x === n -1 && y === m - 1) return dist;
    for(let i = 0; i < 4; i++){
      const nx = x + dx[i];
      const ny = y + dy[i];

      if(
        nx >= 0 && ny >= 0 &&
        nx < n && ny < m &&
        maps[nx][ny] === 1 &&
        !visited[nx][ny]
      ){
        visited[nx][ny] = true;
        queue.push([nx, ny, dist + 1]);
      }
    }
  }
  return -1; // 길 없음
}

5. 단어 변환(Lv.3)

단어 변환은 begin, target과 단어의 집합 words, 총 3개의 매개변수를 통해 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾는 함수를 쓰는 문제다.

최단거리를 탐색하는 것이기 때문에 BFS가 적합하며, 각각의 단어들을 정점으로 해서 한 글자만 다른 단어끼리 연결해서 begin부터 target까지 어떻게 갈 수 있는지 최단거리를 찾으면 된다.

javascript
function isOneLetterDiff(a, b){
  let diff = 0;
  for(let i = 0; i < a.length; i++){
    if(a[i] !== b[i]) diff++;
    if(diff > 1) return false;
  }
  return diff === 1;
}

function solution(begin, target, words){
  if(!words.includes(target)) return 0;

  const queue = [[begin, 0]];
  const visited = new Set(); // 배열로 관리해도 되나, 성능상 set이 유리

  while(queue.length > 0){
    const [current, count] = queue.shift();

    if(current === target) return count;

    for(const word of words){
      if(!visited.has(word) && isOneLetterDiff(current, word)){
        visited.add(word);
        queue.push([word, count + 1]);
      }
    }
  }
  return 0; // 도달 불가능한 경우
}

6. 여행경로

여행경로는 항공권 정보가 담긴 2차원 배열 tickets를 받아 방문하는 공항 경로를 배열로 반환하는 문제다. 가능한 경로가 여럿이면 알파벳 순서상 앞서는 경로를 반환하고, 모든 항공권을 경로상에 포함해야 한다.

이 문제의 핵심은 3가지다.

  1. 그래프 구성: 출발지를 key로, 도착지를 value 배열로(하나의 출발지에서 여러 도착지가 있을 수 있으므로)
  2. 알파벳 순 정렬: 도착지를 사전순으로 정렬해야 한다.
  3. 백트래킹(DFS): 항공권을 하나씩 써가며 경로를 탐색하고, 모든 티켓을 쓰면 return한다.

따라서 아래의 순서로 코드를 작성한다.

  1. 티켓 정보를 토대로 그래프를 만든다.
  2. 각 출발지의 도착지 리스트를 정렬한다.
  3. DFS로 경로를 탐색하며 티켓을 하나씩 사용한다.
  4. 모든 티켓을 다 사용한 경로가 나오면 해당 경로를 반환한다.

예를 들어, 아래의 입력값을 받았다고 하면

javascript
const tickets = [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]

반환하는 경로는 ICN → JFK → HND → IAD여야 한다.

javascript
function solution(tickets) {
    const graph = {};

    // 1. 그래프 구성
    for (let [from, to] of tickets) {
        if (!graph[from]) graph[from] = [];
        graph[from].push(to);
    }

    // 2. 사전순 정렬 (오름차순)
    for (let from in graph) {
        graph[from].sort();
    }

    const route = [];
    const totalTickets = tickets.length;

    let found = false;

    // 3. DFS 백트래킹
    function dfs(curr, path) {
        if (found) return; // 가장 먼저 찾은 사전순 경로만 사용
        if (path.length === totalTickets + 1) {
            route.push(...path);
            found = true;
            return;
        }

        const nextList = graph[curr];
        if (!nextList) return;

        for (let i = 0; i < nextList.length; i++) {
            const next = nextList[i];
            if (next === null) continue; // 이미 사용된 티켓

            nextList[i] = null; // 티켓 사용 처리
            dfs(next, [...path, next]);
            nextList[i] = next; // 백트래킹 (복구)
        }
    }

    dfs("ICN", ["ICN"]);
    return route;
}
Previous해시
ITJavascript
NextNo next post