1260번: DFS와 BFS

문제 접근 🤔

• 연결된 간선을 나타낼 수 있는 그래프를 만든다.

• 작은 정점부터 먼저 방문한다는 조건을 맞추기 위해서 정점을 오름차순으로 정렬한다.

• DFS

  • 시작 노드를 start 라 하고, 노드의 방문 여부를 나타낼 visited 리스트를 선언한다.
  • visited 에 start 를 추가해주고 start 에 연결되어 있고 아직 방문하지 않은 노드들을 같은 방법으로 방문한다.
  • 모든 노드를 방문하고 나면 visited 를 반환한다.

• BFS
  - DFS와 마찬가지로 시작 노드를 start 라 하고, 노드의 방문 여부를 나타낼 리스트를 visited 라 하자.
  - 넓이 우선 탐색이기 때문에 탐색할 Queue 를 선언해준다.
  - 큐에 정점이 존재한다면 큐의 맨 앞 원소를 꺼내어주고 다음 방문할 node 로 선언한다.
  - 방문하지 않은 노드라면 노드에 연결된 정점들을 방문 처리하고 큐에 정점을 추가해준다.
  - 모든 노드를 방문하고 나면 visited 를 반환한다.
  
  
  

놓쳤던 부분 😅

• 두번째 테스트 케이스에서 답이 다르게 나와서 오잉했는데 입력으로 주어지는 간선이 정렬이 안 되어있기 때문에 발생한 문제였다.
  
  
  

코드 😁

파이썬 코드(208 ms)

from collections import deque

N, M, V = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    start, end = list(map(int, input().split()))
    graph[start].append(end)
    graph[end].append(start)

# DFS
def dfs(start, visited = []):
    visited.append(start)
    for next in sorted(graph[start]):
        if next not in visited:
            dfs(next, visited)
    return visited

# BFS
def bfs(start):
    visited = [start]
    q = deque([start])

    while q:
        node = q.popleft()
        for next in sorted(graph[node]):
            if next not in visited:
                visited.append(next)
                q.append(next)
    return visited

# 리스트 출력 형식 변환
def changeStr(numlist):
    return ' '.join(list(map(str, numlist)))

print(changeStr(dfs(V)), changeStr(bfs(V)), sep='\n')

자바스크립트 코드(248 ms)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const [L, ...datas] = fs.readFileSync(filePath).toString().trim().split('\n');

const solution = (N, M, V, list) => {
  const graph = Array.from({ length: N + 1 }, () => []);
  list.forEach((pair) => {
    graph[pair[0]].push(pair[1]);
    graph[pair[1]].push(pair[0]);
  });

  // DFS
  const dfs = (start, visited = []) => {
    visited.push(start);
    graph[start]
      .sort((a, b) => a - b)
      .forEach((next) => {
        if (!visited.includes(next)) {
          dfs(next, visited);
        }
      });
    return visited;
  };

  // BFS
  const bfs = (start) => {
    const visited = [start];
    const q = [start];

    while (!!q.length) {
      let node = q.shift();
      graph[node]
        .sort((a, b) => a - b)
        .forEach((next) => {
          if (!visited.includes(next)) {
            visited.push(next);
            q.push(next);
          }
        });
    }
    return visited;
  };
  console.log([dfs(V).join(' '), bfs(V).join(' ')].join('\n'));
};

solution(
  ...L.split(' ').map(Number),
  datas.map((x) => x.split(' ').map(Number))
);