11403번: 경로찾기

 

11403번: 경로 찾기

 

 

경로 찾기

 

문제

가중치 없는 방향 그래프 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

 

 

---

풀이 

 

문제는 간단하다.

 

• 정점(i, j)에서 i에서 j로 가는 길이 양수인 경로가 있는 지 탐색한다.
• 있다면 1, 없다면 0으로 출력

 

예제를 확인해보자.

 

예제 1은 다음과 같다.

3
0 1 0
0 0 1
1 0 0

 

예제를 다음과 같이 가능한 경로로 표현해보자.

문제가 i에서 j로 가는 경로이니 행이 i, 열이 j가 된다.

 

 

 

i에서 j로 가는 길 중 양수가 있는 경로는 다음과 같다.

0 -> 0 으로 가는 것도, 0->1, 1->2, 2->0 으로 이동하며 결과적으로 0->0으로 이동할 수 있기 때문에 1로 출력된다.

 

다음과 같이 가능한 경로를 연결해보자. 노드가 총 3개 0,1,2이며 이동할 수 있는 경로는 아래와 같다.

 

 

1 1 1
1 1 1
1 1 1

 

 

 

---

설계

문제의 "i에서 j로 가는 길에 1인 경로가 있는 지 탐색한다."는 즉, "i에서 j로 가는 길이 가능한가"로 생각하면 된다.

처음 입력받는 배열에서 1인 값을 가능한 경로로 생각하자.

 

예제 2의 가능한 경로를 다음과 같이 linkedList로 표현할 수 있다.

 

 

 

 

만약 0->0경로로 이동이 가능한가를 탐색한다고 하면, 

start가 0이고 end가 0이므로

 

1. 0->3 (탐색)
2. 3->4,5 (3노드와 연결된 4와 5 탐색)
3. 4->0, 5->6

start가 0이면서 end가 0인 경로가 존재한다. 

따라서 1을 출력하면 된다. 

 

 

 

 

 

---

구현

 

 

 

위의 설계를 바탕으로 코드를 구현해보자.

 

고려해야할 점이 있다. start와 end가 같은 경우를 고려해야 한다.

start부터 연결된 경로로 이동하며 탐색을 하는 건 맞지만, 방문처리를 해주지 않으면 코드가 무한반복하게 된다.

 

예를 들어 예제 2에서 0->0의 경로가 가능한지 탐색할 때, 방문처리를 해주지 않으면 코드가 무한루프에 빠지게 된다.

 

그래서 다음과 같이 방문처리를 하기 위한 visited[]배열을 사용하였다.

 

• queue를 이용해 해당 경로에 연결된 모든 경로를 탐색
• 탐색한 값과 end가 같다면 1을 출력

 

 

 

 

 

 

---

전체코드

 

 

let N = Int(readLine()!)!

var linkedList = [[Int]](repeating: [Int](), count: N)
var result = [[Int]](repeating: [Int](repeating: 0, count: N), count: N)

for i in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }

    for j in 0..<input.count {
        if input[j] == 1 {
            linkedList[i].append(j)
        }
    }
}

for i in 0..<N {
    for j in 0..<N {
        result[i][j] = find(i, j, linkedList)
    }
}

func find(_ start: Int, _ end: Int, _ graph: [[Int]]) -> Int {
    var visited = [Bool](repeating: false, count: N)
    var queue = [Int]()

    queue.append(start)

    while !queue.isEmpty {
        let current = queue.removeFirst()

        for neighbor in graph[current] {
            if !visited[neighbor] {
                if neighbor == end {
                    return 1
                }

                queue.append(neighbor)
                visited[neighbor] = true
            }
        }
    }

    return 0
}

for i in 0..<N{
    for j in 0..<N{
        print((result[i][j]), terminator: " ")
    }
    print("")
}