[Kotlin, S1] 백준 11403번 경로 찾기

출처: unsplash.com

 

경로 찾기(11403번)

Silver 1

#그래프 이론 #그래프 탐색 #최단 경로 #플로이드-워셜

https://www.acmicpc.net/problem/11403

 

문제 내용

 

 

문제 접근

그래프에서 정점의 개수 N이 주어진다.

입력 리스트 크기는 N * N이고, 한 줄에 정점이 여러 개이거나 없을 수도 있다.

i번째 줄에 정점이 있으면 i번째 줄의 j번째 데이터에 있을 건데, j번째 줄의 입력값으로 가서 정점이 존재하는지 확인하는 작업을 해야 한다.

자세하게 설명하자면, 입력 예제 2를 예로 들겠다.

7
0 0 0 1 0 0 0	// 3
0 0 0 0 0 0 1	// 6
0 0 0 0 0 0 0	//
0 0 0 0 1 1 0	// 4, 5
1 0 0 0 0 0 0	// 0
0 0 0 0 0 0 1	// 6
0 0 1 0 0 0 0	// 2

7이 정점의 개수이므로 입력은 7 * 7로 입력된다.

리스트로 입력받기 때문에 0번째 줄부터 확인을 해보면 0번째 줄에는 3번째 값에 정점이 존재한다.

그러면 입력받은 값의 3번째 줄로 이동한다. 3번째 줄에는 4, 5번째에 정점이 존재한다.

2가지가 존재하므로 먼저 4번째 줄로 이동해 보면 0번째 값에 정점이 있기 때문에 0번째 줄로 가는데, 이 때는 이미 지나왔던 데이터이므로 종료되게 된다.

 

그러면 지금까지 0 -> 3 -> 4 순서대로 이동하였다.

이로 인해 0번째 줄에는 3, 4번째 데이터가 간선이 되는 것이기 때문에 1로 바꿔주면 아래와 같다.

1 0 0 1 1 0 0

이제 아까 3번째 줄을 지났을 때 4, 5번째 줄을 확인했기 때문에 이제 5번째 줄을 확인한다.

5번째 줄에는 6번째에 정점이 있으므로 6번째 줄로 이동하면 2번째 값이 정점이기 때문에 2번째 줄로 이동한다.

2번째 줄에는 어떤 정점도 존재하지 않기 때문에 종료되게 된다.

방금까지의 이동으로 5 -> 6 -> 2 순으로 이동했기에 기존 변경된 리스트에 새롭게 1을 추가해 주면 최종적인 리스트는 아래와 같다.

1 0 1 1 1 1 1 1

출력 예제 2의 첫 줄과 동일해진 것을 확인할 수 있다.

아래의 6줄도 모두 같은 과정을 반복하면 된다.

 

이 과정은 플로이드 워셜 알고리즘을 이용하면 쉽게 해결할 수 있지만, 플로이드 워셜 알고리즘을 모르고 있어도 그래프 탐색 알고리즘으로 해결할 수 있다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList
import java.util.Queue

private var graph = arrayOf<List<Int>>()
private var result = arrayOf<Int>()
private var visited = booleanArrayOf()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val point = readLine().toInt()

    graph = Array(point) { listOf() }
    result = Array(point) { 0 }
    visited = BooleanArray(point)

    for (i in 0 until point) {
        val path = readLine().split(" ").map { it.toInt() }
        graph[i] = path
    }

    for (i in graph.indices) {
        for (j in graph[i].indices) {
            if (!visited[i] && graph[i][j] == 1) {
                bfs(j)
            }
        }
        println(result.joinToString(" "))

        visited.fill(false)
        result.fill(0)
    }
}

private fun bfs(x: Int) {
    val queue: Queue<Int> = LinkedList()
    queue.add(x)
    result[x] = 1
    visited[x] = true

    while (queue.isNotEmpty()) {
        val dataX = queue.poll()

        for (i in 0 until graph[dataX].size) {
            if (!visited[i] && graph[dataX][i] == 1) {
                visited[i] = true
                queue.add(i)
                result[i] = 1
            }
        }
    }
}

 

문제 풀이

입력값을 저장하기 위한 graph를 생성한다.

출력을 줄마다 개별로 하기 위해 result를 생성해 주고, result를 이용해 출력을 하기 때문에 visited는 2차원 배열로 만들 필요가 없다.

 

처음에 값을 graph에 입력받아 주고 2중 반복을 돌아서 bfs 함수를 수행한다.

j번째 값의 visited가 false일 때와 graph의 값이 1일 때만 수행한다. 한 줄에 1(정점)이 여러 개 있을 수도 있어서 1번만 호출하면 안 된다.

 

bfs에서는 queue를 이용해 조건에 맞는 데이터를 삽입한다.

초기에 파라미터값을 queue에 넣어 주고, queue가 빌 때까지 계속 순회한다.

queue에 넣는 조건은 위의 조건과 동일하다. dataX 변수에 graph의 몇 번째 줄을 탐색해야 하는지 파악하고, dataX번째 줄에 1이 있고, 1이 몇 번째 값인지 확인해 동일한 index의 visited가 false인 것을 만족해야 한다.

queue에 값을 넣고, 간선을 1로 표시해 준다.

 

bfs 종료 후 변경된 result List를 출력한다.

출력 후, result와 visited를 초기의 형태로 초기화한다. 다음 값에 써야 하니까.

 

 

문제 해결 과정

문제 이해가 제일 어렵다..

설명이 뭔가 두루뭉술했던 것 같다. 그냥 나의 까막눈 이슈일 수도 있다.

문제 이해가 너무 어려워서 문제 접근법을 좀 찾아보니까 바로 이해가 되더라.