[코딩테스트]백준 - 경로찾기

경로찾기

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제 입력 1

3
0 1 0
0 0 1
1 0 0

예제 출력 1

1 1 1
1 1 1
1 1 1

예제 입력 2

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

예제 출력 2

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: degurii

알고리즘 분류

• BFS
• DFS
• 플로이드 와샬 알고리즘

해결한 코드

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
var n = input[0] / 1
var graph = []
for (var i = 1; i < input.length; i++) {
    graph.push(input[i].split(' '))
}
if (n === 1) { // n이 1개면 해당 숫자 출력 
    console.log(...graph[0])
} else {
    var visit = []
    for (var i = 0; i < n; i++) {
        visit.push(Array(n).fill(false))
    }

    function initVisit() { // visit을 초기화 해주는 함수
        for (var i = 0; i < n; i++) {
            for (var j = 0; j < n; j++) {
                visit[i][j] = false
            }
        }
        return visit
    }
    function setOneOrZeroAsElements(result) { // 1, 0으로 행 만들기 
        var str = Array(n).fill('0')
        for (var i = 0; i < result.length; i++) {
            str[result[i]] = '1'
        }
        return str.join(' ')
    }
    var answer = ''
    for (var i = 0; i < n; i++) {
        var result = []
        visit = initVisit() // 새로운 i마다 visit 초기화 
        dfs(i, result) // dfs 방법
        // result = bfs(i, result) // bfs 방법 
        answer += setOneOrZeroAsElements(result) + '\n' // i행의 문자열을 붙이고 줄바꿈 
    }
    console.log(answer.trim())

    function dfs(vertex, result) {
        var currentRow = graph[vertex]
        var currentVisit = visit[vertex]
        for (var i = 0; i < n; i++) {
            if (currentRow[i] === '1' && currentVisit[i] === false) {
                result.push(i)
                currentVisit[i] = true
                dfs(i, result)
            }
        }
        return result
    }

    function bfs(vertex, result){
        var q = []
        var currentRow = []
        var currentVisit = []
        currentVisit[vertex] = true
        q.push(vertex)
        while(q.length !== 0){
            vertex = q.shift()
            currentVisit = visit[vertex]
            currentRow = graph[vertex]
            for(var i=0; i<currentRow.length; i++){
                if(currentRow[i] === '1' && currentVisit[i] === false){
                    currentVisit[i] = true
                    q.push(i)
                    result.push(i)
                }
            }
        }
        return result
    }
}

풀이

※ 플로이드와샬을 익히려고 했는데 dfs, bfs로 풀어버렸다..

1. DFS

1. 모든 정점에 대하여 연결경로를 탐색한다.

• 0부터 n까지의 정점에 대한 그래프가 들어온다.
  그림으로 표현하면 다음과 같다.
  
• 정점 0의 경로는 그래프[0]에서 값이 '1'인 경우
  • 그래프[0]에서 값이 '1'인 인덱스가 정점 0과 연결된 정점
    
  • 위 예시에서 인덱스 3이 '1' 이므로, 0과 연결된 정점은 3
    ✔ 해당 정점을 방문했다는 체크 해주기
  • 정점 3으로 가서 그래프[3] 가운데 값이 '1'인 경우를 탐색
    • 그래프[3]에서 값이 '1'인 인덱스가 정점 3과 연결된 정점
      
    • 위 예시에서 인덱스 4와 5가 '1'이므로, 0과 연결된 정점은 4, 5
      dfs니까 일단 4부터 탐색
      ✔ 해당 정점을 방문했다는 체크 해주기

• 이런식으로 연결된 정점을 탐색하는 것이다.
  
  이렇게 정점 0의 dfs 탐색이 끝나면 정점 1에 대한 dfs 탐색을 시작한다.
  이를 정점 n-1(마지막) 까지 진행한다.

2. 탐색한 정점을 저장한다.

• 나는 result라는 배열을 만들어 탐색시마다 저장했다.
  다음 정점 탐색을 들어갈때마다 (ex. 정점 0의 dfs 탐색이 끝나고 정점 1의 dfs 탐색을 들어갈 때) result를 초기화해주었다.

3. result 배열에 정점 숫자가 있으면 1, 없으면 0을 넣어 문자열로 만든다.

• 이를 위해 n크기의 임시 배열을 만들었다.
  모든 원소 값을 '0'으로 만들었다.
• result 배열 내에 있는 정점을 임시배열의 인덱스로 하고, 해당 값을 '1'로 주었다.

4. 문자열을 0부터 n까지 줄바꿈하여 붙이고 출력한다.

2. BFS

1. 모든 정점의 연결 경로를 탐색한다.

단, DFS와 달리 BFS는 너비 탐색이다.

• 그림으로 나타내면 다음과 같이 탐색하게 된다.
  
  3에 연결된 4부터 탐색하는 DFS와 달리, 5도 같이 탐색한다.

2. BFS를 구현한다.

• 큐에 시작 정점을 넣기
  • 0부터 n-1을 차례차례 시작한다.
• 연결 정점을 저장할 result 배열 준비
• 큐가 빌때까지
  • 큐의 첫번째 원소를 빼냄 <= 지금 탐색하는 정점
  • 그래프[큐의 첫번째 원소] 에서 '1'인 값을 탐색
    • '1'이면 해당 인덱스를 큐에 넣기
    • result에도 해당 인덱스 넣기
      DFS에서 탐색한 정점을 저장하는 것과 마찬가지이다.

3. result 배열에 정점 숫자가 있으면 1, 없으면 0을 넣어 문자열로 만든다.

• 이를 위해 n크기의 임시 배열을 만들었다.
  모든 원소 값을 '0'으로 만들었다.
• result 배열 내에 있는 정점을 임시배열의 인덱스로 하고, 해당 값을 '1'로 주었다.

4. 문자열을 0부터 n까지 줄바꿈하여 붙이고 출력한다.

맞긴 했지만 뭔가 찝찝하다.
더 좋은 방법이 있을 것 같고, 내 코드는 비교적 비효율적인 느낌이 들기도 하고..
플로이드와샬로는 어떻게 푸는 걸까..