[백준/BOJ] 11403번: 경로 찾기

문제

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

11403번: 경로 찾기

해설

플로이드 와샬 알고리즘을 사용하여 해결할 수 있는 문제이다.

플로이드 와샬 알고리즘의 기본 문제인만큼 플로이드 와샬에 대해 잘 모른다면 플로이드 와샬을 읽어보면 좋을 것이다.

 

0이면 간선이 존재하지 않고, 1이면 간선이 존재한다.

그렇다면 예시를 들어보자.

1 - 3은 간선이 없다하고, 1 - 2와 2 - 3은 간선이 있다고 하자.

그렇다면 1 - 2는 1이고 2 - 3은 1이므로 1 - 2 - 3이 되어 1 - 3은 간선이 존재하게 된다.

즉, arr[i][k] == 1, arr[k][j] == 1이면 arr[i][j] 또한 1이 된다.

코드

import java.util.*

private lateinit var check: Array<IntArray>

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    check = Array(n) { IntArray(n) }

    repeat(n) { i ->
        val st = StringTokenizer(readLine())
        repeat(n) { j ->
            check[i][j] = st.nextToken().toInt()
        }
    }

    floydWarshall(n)
}

private fun floydWarshall(n: Int) {
    repeat(n) { k->
        repeat(n) { i ->
            repeat(n) { j ->
                if(check[i][k] == 1 && check[k][j] == 1) check[i][j] = 1
            }
        }
    }

    repeat(n) { i ->
        repeat(n) { j ->
            print("${check[i][j]} ")
        }
        println()
    }
}