백준 - 1260 DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

• 첫째 줄
  • 정점의 개수 N
  • 간선의 개수 M
  • 탐색을 시작할 정점의 번호 V
• M개의 줄
  • 간선이 연결하는 두 정점의 번호

제한 조건

• 1 ≤ N ≤ 1,000
• 1 ≤ M ≤ 10,000
• 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문

예시

// NOTE: 입력
4 5 1
1 2
1 3
1 4
2 4
3 4

// NOTE: 출력
1 2 4 3
1 2 3 4

// NOTE: 입력
5 5 3
5 4
5 2
1 2
3 4
3 1

// NOTE: 출력
3 1 2 5 4
3 1 4 2 5

해결

고민한 부분

1. graph 생성

   • 입력된 데이터가 인접 행렬이나 인접 리스트로 들어온 게 아니라서 graph 생성
   • Map과 Set 사용
     • key 유무를 확인하기 쉬운 Map 이용
     • 인접 노드값은 중복이 없도록 Set 이용

2. 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문

   • 방문할 queue에 인접 노드 넣어줄 때 정렬하여 넣어줌

오래 걸린 이유

1. 출력 형식

   • 띄어쓰기로 구분한 string으로 출력

2. 예외 처리

   • start의 노드에 간선이 없는 경우

   // NOTE: 입력
   3 1 1
   2 3
   
   // NOTE: 출력
   1
   1

전체 코드

// NOTE: inputs
let [_conditions, ..._inputs] = require('fs')
    .readFileSync('dev/stdin')
    .toString()
    .trim()
    .split(/\n/);

// NOTE: solution
const getGraphMap = (inputData) => {
    const _map = new Map();
    
    for (let input of inputData) {
        const [_from, _to] = input.split(' ').map(Number);
    
        if (!_map.has(_from)) _map.set(_from, new Set());
        if (!_map.has(_to)) _map.set(_to, new Set());
        
        _map.get(_from).add(_to);
        _map.get(_to).add(_from);
    }
    
    return _map; 
};

const dfs = (graph, startNode) => {
    let _visited = [];
    let _needVisit = [];
    
    _needVisit.push(startNode);
    
    while(_needVisit.length > 0) {
        const _node = _needVisit.shift();
        
        if (!_visited.includes(_node)) {
            _visited.push(_node);
            
            if (!graph.has(_node)) break;
                
            const _adjacentNode = [...graph.get(_node)].sort((a, b) => a - b);
            _needVisit = [..._adjacentNode, ..._needVisit];
        }
    }
    
    return _visited;
};

const bfs = (graph, startNode) => {
    let _visited = [];
    let _needVisit = [];
    
    _needVisit.push(startNode);
    
    while(_needVisit.length > 0) {
        const _node = _needVisit.shift();
        
        if (!_visited.includes(_node)) {
            _visited.push(_node);
            
            if (!graph.has(_node)) break;
            
            const _adjacentNode = [...graph.get(_node)].sort((a, b) => a - b);
            _needVisit = [..._needVisit, ..._adjacentNode];
        }
    }
    
    return _visited;
};

const _graphMap = getGraphMap(_inputs);
const [, , v] = _conditions.split(' ');

console.log(dfs(_graphMap, +v).join(' '));
console.log(bfs(_graphMap, +v).join(' '));

---

출처

• 1260번: DFS와 BFS
• 1260번 TypeError