[코딩테스트]백준 - DFS와 BFS

DFS와 BFS

문제

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

입력

• 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다.
• 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
• 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

• 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다.
• V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2

3 1 2 5 4
3 1 4 2 5

예제 입력 3

1000 1 1000
999 1000

예제 출력 3

1000 999
1000 999

출처

• 문제를 만든 사람: author5
• 데이터를 추가한 사람: djm03178 doju
• 어색한 표현을 찾은 사람: doju
• 빠진 조건을 찾은 사람: pumpyboom

알고리즘 분류

• BFS
• DFS

1. DFS - 재귀

해결한 코드

function b1260() {
    var fs = require('fs');
    var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
    // var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
    var info = input[0].split(' ')
    var n = info[0] / 1
    var m = info[1] / 1
    var startV = info[2] / 1
    var link = []
    for (var i = 1; i < input.length; i++) {
        link.push(input[i].split(' ').map(e => e = e / 1))
    }
  
    var graph = makeGraph(n, link) // 인접 행렬의 모습으로 그래프 만들기
   
    var visit = Array(n).fill(false) // 방문 여부를 체크할 visit 배열
    var result = [] // dfs결과를 담을 result 배열 
    var d = dfs(startV, visit, graph, result) 
    
    visit = Array(n).fill(false) // visit 초기화
    result = [] // result 초기화. 이제 여기에 bfs결과를 담을 것임 
    var b = bfs(startV, visit, graph, result)
    
    console.log(d.join(' '))
    console.log(b.join(' '))
}

function dfs(startV, visit, graph, result) {
    result.push(startV)
    visit[startV - 1] = true
  // 맨 처음 시작하는 vertex를 result에 담고 방문 여부를 true로 바꿔줌 
  
    var current = startV - 1
    for (var i = 0; i < graph[0].length; i++) {
        if (graph[current][i] == 1 && visit[i] == false) {
          // 현재 vertex와 연결되어있고, 방문도 안했으면 
            dfs(i + 1, visit, graph, result)
          // 해당 vertex 재귀로 방문하기 
        }
    }
    return result
}

function bfs(startV, visit, graph, result) {
    var q = []
    // bfs로 순회하기 위한 큐
    q.push(startV)
    visit[startV - 1] = true
  // 시작 vertex를 큐에 넣고 방문 여부를 true로 바꿈 
    while (q.length !== 0) {
        var current = q.shift()
        result.push(current)
      // 큐의 가장 첫번째에 있는 원소를 뽑아 현재 vertex로 지정 
        for (var i = 0; i < graph[0].length; i++) {
            if (graph[current - 1][i] == 1 && visit[i] == false) {
              // 현재 vertex와 연결되었으면서 방문하지 않은 vertex가 있으면 
                q.push(i + 1)
              // 큐에 넣고 
                visit[i] = true
              // 방문 여부 true로 바꿈 
            }
        }
    }
    return result
}

function makeGraph(n, link) {
  // 인접행렬로 그래프를 만드는 함수
  
    var arr = []
    for (var i = 0; i < n; i++) {
        arr.push(Array(n).fill(0))
    }
  // arr는 2차원 배열이 됨 
  
    for (var i = 0; i < link.length; i++) {
        var x = link[i][0]
        var y = link[i][1]
        if (arr[x - 1][y - 1] === 0 && arr[y - 1][x - 1] === 0) {
            arr[x - 1][y - 1] = 1
            arr[y - 1][x - 1] = 1
        }
      // 무방향 그래프 형식으로 연결시킴 
    }
    return arr
}

b1260()

알고리즘

※ DFS, BFS의 원리를 이해한다.

1. 입력으로 받은 정점과 간선 연결에 따른 그래프를 만든다.

ex. 만약 정점과 간선 연결의 정보가 다음과 같다면

link = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 4],
  [3, 4]
]

인접 행렬의 모습으로 이차원배열을 다음과 같이 만들 수 있다.

 graph = [ 
   [ 0, 1, 1, 1 ], 
   [ 1, 0, 0, 1 ], 
   [ 1, 0, 0, 1 ], 
   [ 1, 1, 1, 0 ] 
 ]

이렇게 그래프 배열을 만들어준다.

2. dfs를 구현한다.

우선, dfs를 구현하려면 다음 사항들이 필요하다.

• 위에서 구현한 graph
• 방문 여부를 따질 visit 배열
• 순회 결과를 차례로 넣을 result 배열

visit = [false, false, false, false]

(참고) visit[0]은 vertex 1에 대한 방문 내용, visit[1]은 vertex 2에 대한 방문 내용이다.

2-1. 시작 정점은 1이고, 1부터 dfs로 순회한다면,

 graph = [ 
   [ 0, 1, 1, 1 ], <= 여기가 vertex 1의 연결 정보 
   [ 1, 0, 0, 1 ], <= vertex 2의 정보
   [ 1, 0, 0, 1 ], <= vertex 3의 정보
   [ 1, 1, 1, 0 ] <= vertex 4의 정보
 ]

• 현재 1을 순회하니까 result 배열에 1을 넣는다.
• visit[0] = true 를 해주어 현재 vertex 1에 방문했음을 표시한다.
• vertex 1과 연결된 vertex는?
  [ 0, 1, 1, 1 ]이므로, 인덱스값이 1, 2, 3인 곳이 1인 것으로 보아, vertex 2, 3, 4와 연결되어있음을 알 수 있다.
• 그 vertex들 중 visit이 false인 것은?
  현재 visit = [true, false, false, false]이므로, vertex 2, 3, 4 모두 false이다.
  👉🏻 그럼 값이 작은 2를 다음으로 방문한다.

2-2. 이제 시작 정점으로 2가 들어왔다.

• 현재 2를 순회하니까 result 배열에 2를 넣는다.
• visit[1] = true를 해주어 현재 vertex 2에 방문했음을 표시한다.
• vertex 2와 연결된 vertex는?
  [ 1, 0, 0, 1 ]이므로, 인덱스 값이 0, 3인 곳이 1인 것으로 보아, vertex 1, 4와 연결되어있음을 알 수 있다.
• 그 vertex들 중 visit이 false인 것은?
  현재 visit = [true, true, false, false]이므로, vertex 4가 false이다.
  👉🏻 4를 다음으로 방문한다.

2-3. 이제 시작 정점으로 4가 들어왔다.

• 현재 4를 순회하니까 result 배열에 4를 넣는다.
• visit[3] = true를 해주어 현재 vertex 4에 방문했음을 표시한다.
• vertex 4와 연결된 vertex는?
  [ 1, 1, 1, 0 ]이므로, 인덱스 값이 0, 1, 2인 곳이 1인 것으로 보아, vertex 1, 2, 3과 연결되어있음을 알 수 있다.
• 그 vertex들 중 visit이 false인 것은?
  현재 visit = [true, true, false, true]이므로, vertex 3이 false이다.
  👉🏻 3을 다음으로 방문한다.

2-4. 이제 시작 정점으로 3이 들어왔다.

• 현재 3을 순회하니까 result 배열에 3을 넣는다.
• visit[2] = true를 해주어 현재 vertex 3에 방문했음을 표시한다.
• vertex 3과 연결된 vertex는?
  [ 1, 0, 0, 1 ]이므로, 인덱스 값이 1, 3인 곳이 1인 것으로 보아, vertex 1, 4와 연결되어있음을 알 수 있다.
• 그 vertex들 중 visit이 false인 것은?
  현재 visit = [true, true, true, true]이므로, 모두 다 방문했다.

2-5. 모두 다 방문했으므로 result 배열을 return 한다.

result = [ 1, 2, 4, 3 ]

3. bfs를 구현한다.

bfs를 구현하기 위해서는 다음 사항들이 필요하다.

• 방문 여부를 따질 visit 배열
• 다음 순회할 vertex를 뽑을 큐(queue)
• 순회 결과를 차례로 넣을 result 배열
  ✔ visit과 result는 dfs랑 같은 기능이다...

3-1. 시작 정점은 1이고, 1부터 bs로 순회한다면,

 graph = [ 
   [ 0, 1, 1, 1 ], <= 여기가 vertex 1의 연결 정보 
   [ 1, 0, 0, 1 ], <= vertex 2의 정보
   [ 1, 0, 0, 1 ], <= vertex 3의 정보
   [ 1, 1, 1, 0 ] <= vertex 4의 정보
 ]

• 현재 1을 순회하니까 result 배열에 1을 넣는다.
• visit[0] = true를 해주어 방문했음을 체크한다.

visit = [true, false, false, false]

• vertex 1과 연결된 vertex는?
  [ 0, 1, 1, 1 ]이므로, vertex 2, 3, 4와 연결되어있다.
• 그 중 방문하지 않은 vertex는? (알다시피) 아직 방문한 애 하나도 없다...
• 연결된 vertex들을 큐에 넣는다.

queue = [ 2, 3, 4 ]

• 큐에 넣은 vertex들에 대하여 방문했음을 체크한다.

visit = [true, true, true, true]

3-2. 다음으로 순회할 vertex는 큐에서 뺀 첫번째 원소이다.

queue = [ 3, 4 ]

(참고) 큐는 선입선출 형식으로 구성된다. 따라서 큐에서 원소를 하나 빼면, 걔는 맨 처음 넣었던 원소가 된다.
고로 다음 순회하는 vertex는 2

• 현재 2를 순회하니까 result 배열에 2를 넣는다.
• vertex 2와 연결된 vertex는?
  [ 1, 0, 0, 1 ]이므로, 1, 4와 연결되어있다.
• 그 중 방문하지 않은 vertex는?
  현재 visit 배열은 모두 true이다. 방문하지 않은 vertex가 없음 !! 다 방문했어 !!!
• 그럼 그냥 패쓰한다.

3-3. 다음으로 순회할 vertex는 큐에서 뺀 첫번째 원소 3

queue = [ 4 ]

• 현재 3을 순회하니까 result 배열에 3을 넣는다.
• vertex 3과 연결된 vertex는?
  [ 1, 0, 0, 1 ]이므로, 1, 4와 연결되어있다.
• 그 중 방문하지 않은 vertex는? 없어!! 없어!!
• 그냥 패쓰

3-4. 다음으로 순회할 vertex는 큐에서 뺀 첫번째 원소 4

queue = [ ]

• 현재 4를 순회하니까 result 배열에 4를 넣는다.
• vertex 4와 연결된 vertex는?
  [ 1, 1, 1, 0 ]이므로, 1, 2, 3과 연결되어있다.
• 그 중 방문하지 않은 vertex는? 없다~
• 패쓰

3-5. 큐가 비었다. 종료한다.
그대로 result를 return한다.

4. 이렇게 dfs, bfs로 순회해서 얻은 result 값을 공백 포함한 문자열로 만들어 출력한다.

DFS는 사실 스택으로 구현한다...
(본래 이게 정석. 재귀로도 짤 수 있는건 스택으로 짠 DFS랑 결국 순회 매커니즘이 같기 때문... 좀 더 간결한 코드를 짤 수 있기도 하고)

2. DFS - 스택

해결한 코드

function b1260() {
    var fs = require('fs');
    var input = fs.readFileSync('/dev/stdin').toString().trim();
    // var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
    var temp = input.split('\n')
    var info = temp[0].split(' ')
    var n = info[0] / 1
    var m = info[1] / 1
    var startV = info[2] / 1
    var link = []
    for (var i = 1; i < temp.length; i++) {
        link.push(temp[i].split(' ').map(e => e / 1))
    }
    var graph = makeGraph(n, link)
    // 여기까지 코드 동일 
    
    var d = stackDfs(startV, graph, n)
    
    var b = bfs(startV,graph, n) // visit, result 배열을 bfs 함수 안에서 선언했을 뿐 사싱살 동일 
    
    console.log(d.join(' '))
    console.log(b.join(' '))
}

function stackDfs(startV, graph, n){
    var visit = Array(n).fill(false)
    var result = []
    var stack = []
    
    visit[startV-1] = true
    result.push(startV)
    stack.push(startV)
     
    while(stack.length!==0){
        var current = stack[stack.length-1]
        var flag = false
        for(var i=0; i<graph[0].length; i++){
            if((graph[current-1][i] == 1) &&(visit[i]== false)){
                stack.push(i+1)
                visit[i] = true
                result.push(i+1)
                flag = true
                break
            }
        }
        
        if(flag==false){
            stack.pop()
        }
    }
    
    return result
}

function bfs(startV, graph, n) {
    var visit = Array(n).fill(false)
    var result = []
    var q = []
    
    q.push(startV)
    visit[startV - 1] = true
    
    while (q.length !== 0) {
        var current = q.shift()
        result.push(current)
        
        for (var i = 0; i < graph[0].length; i++) {
            if ((graph[current - 1][i] == 1) && (visit[i] == false)) {
                q.push(i + 1)
                visit[i] = true
            }
        }
    }
    
    return result
}

function makeGraph(n, link) {
    var arr = []
    for (var i = 0; i < n; i++) {
        arr.push(Array(n).fill(0))
    }
    for (var i = 0; i < link.length; i++) {
        var x = link[i][0]
        var y = link[i][1]
        if (arr[x - 1][y - 1] === 0 && arr[y - 1][x - 1] === 0) {
            arr[x - 1][y - 1] = 1
            arr[y - 1][x - 1] = 1
        }
    }
    return arr
}

b1260()

알고리즘

※ DFS, BFS의 원리를 이해한다.

1. 그래프를 그린다.

• "1. DFS - 재귀" 과정과 동일하다.

2. dfs를 구현한다.

dfs 구현을 위해 다음 사항들이 필요하다.

• 방문 여부를 체크할 visit 배열
• 순회 결과를 차례로 넣을 result 배열
• 순회 중 방문한 vertex를 넣고 빼면서 방문하지 않은 인접 vertex가 있는지 확인하는 stack

2-1. (시작 정점인) vertex 1을 순회한다.

• 방문 여부를 체크한다. visit[0] = true
• 현재 1을 순회하니까 result 배열에도 1을 넣는다.
• 스택에도 현재 vertex인 1을 넣는다.

stack = [1]

• vertex 1과 연결되었으면서 visit 여부가 false인 vertex는?
  2, 3, 4가 연결되어있으면서 모두 visit이 false이다.
  👉🏻 이 중 첫번째 vertex인 2를 다음으로 순회할 것이다. 따라서,
  ✔ stack에 2를 넣고,
  ✔ visit[1]의 방문 여부를 true로 바꾸고,
  ✔ result 배열에 2를 넣는다.
  📍 그리고 위 과정을 거쳤다는 표시인 flag = true를 해준다.

🖐🏻 flag? 그걸 왜 해?
과정을 진행하다보면 전체 vertex는 다 방문하지 않았는데, 현재 vertex와 연결된 vertex들은 모두 다 방문한 경우가 생길 수 있다.
이럴 땐 stack에 넣어두었던 vertex들을 하나씩 pop하여 순회한 순서대로 되돌아가면서 방문하지 않은 인접 vertex가 있는지 확인해야 한다.
따라서, 만약 현재 vertex와 연결된 vertex들이 모두 방문한 것들이라면, stack 안에 있는 vertex를 pop 해주기 위해 flag라는 장치를 사용한 것이다.

2-2. stack에 있는 가장 마지막 원소를 순회한다.

stack = [1, 2]

고로 vertex 2를 순회한다.

• vertex 2와 연결되어있으면서 visit 여부가 false인 vertex는?
  4가 연결되어있으면서 visit이 false다.
  ✔ stack에 4를 넣고
  ✔ visit[3]의 방문 여부를 true로 바꾸고
  ✔ result 배열에 4를 넣는다.
  ✔ flag = true 를 한다.

2-3. stack에 있는 가장 마지막 원소를 순회한다.

stack = [1, 2, 4]

vertex 4를 순회한다.

• vertex 4와 연결되어있으면서 visit 여부가 false인 vertex는?
  3이 연결되어있으면서 visit이 false이다.
  ✔ stack에 3을 넣고
  ✔ visit[2]의 방문 여부를 true로 바꾸고
  ✔ result 배열에 3을 넣는다.
  ✔ flag = true를 한다.

2-4. stack에 있는 가장 마지막 원소를 순회한다.

stack = [1, 2, 4, 3]

vertex 3를 순회한다.

• vertex 3과 연결되어있으면서 visit 여부가 false인 vertex는?
  없다. 모든 vertex를 방문했다.
  👉🏻 flag상태는? false이다.
  ✔ stack을 pop한다.

stack = [1, 2, 4]

2-5. stack에 있는 가장 마지막 원소를 순회한다.
vertex 4와 연결되어있으면서 visit여부가 false인 vertex는?
없다 !
👉🏻 flag 상태는? false이다.
✔ stack을 pop한다.

stack = [1, 2]

2-6. stack에 있는 가장 마지막 원소를 순회한다.
vertex 2와 연결되어있으면서 visit 여부가 false인 vertex는?
없다.. 없어..
👉🏻 flag? false
✔ stack을 pop한다.

stack = [1]

2-7. stack에 있는 가장 마지막 원소를 순회한다.
vertex 1과 연결되어있으면서 visit 여부가 false인 vertex는?
없슴다
👉🏻 flag? false
✔ stack.pop()

stack = [ ]

2-8. stack이 비었으므로 dfs를 종료한다.
result 배열을 return한다.

3. bfs를 구현한다.

• "1. DFS - 재귀" 과정과 동일하다.

4. 이렇게 dfs, bfs로 순회해서 얻은 result값을 공백을 포함한 문자열로 만들어 출력한다.

아무리 반례를 찾아도 다 잘되는데 채점만 하면 틀렸대서 왜그럴까... 했던 문제.
바보같게도 공백을 포함한 문자열로 출력하지 않아서 그랬다. 문제좀 잘 보고 잘 읽자 ㅜㅜ 흑흑