[백준] 파티 (1238)(Kotlin)
문제 설명
N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
입출력 예제1
| 입력 | 출력 |
|---|---|
| 4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3 |
10 |
입출력 예제2
문제 풀이1 (Dijkstra - Adjacency List)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
data class Node(val index: Int, val dist: Int): Comparable<Node> {
override fun compareTo(other: Node): Int {
return this.dist - other.dist
}
}
val adjList: MutableList<PriorityQueue<Node>> = mutableListOf()
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val (n: Int, m: Int, x: Int) = readLine()
.split(" ")
.map { it.toInt() }
repeat(n) { adjList.add(PriorityQueue<Node>()) }
repeat(m) {
val (start: Int, dest: Int, dist: Int) = readLine()
.split(" ")
.map { it.toInt() }
adjList[start - 1].add(Node(dest - 1, dist))
}
var route: Array<IntArray> = Array(n) { intArrayOf() }
for (i in 0 until n)
route[i] = dijkstraMatrix(i, x, n)
var max = 0
for (i in 0 until n)
max = Math.max(route[i][x - 1] + route[x - 1][i], max)
println(max)
}
fun dijkstraMatrix(start: Int, dest: Int, vertex: Int): IntArray {
val queue: PriorityQueue<Node> = PriorityQueue()
var distance: IntArray = IntArray(vertex) { Int.MAX_VALUE }
var check: BooleanArray = BooleanArray(vertex) { false }
queue.add(Node(start, 0))
distance[start] = 0
while (queue.isNotEmpty()) {
val now = queue.poll().index
if (check[now]) continue
check[now] = true
for (node in adjList[now]) {
if (distance[node.index] > distance[now] + node.dist) {
distance[node.index] = distance[now] + node.dist
queue.add(Node(node.index, distance[node.index]))
}
}
}
return distance
}
문제 풀이2 (Dijkstra - Adjacency List)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
data class Node(val index: Int, val dist: Int): Comparable<Node> {
override fun compareTo(other: Node): Int {
return this.dist - other.dist
}
}
val adjList: MutableList<PriorityQueue<Node>> = mutableListOf()
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val (n: Int, m: Int, x: Int) = readLine()
.split(" ")
.map { it.toInt() }
repeat(n) { adjList.add(PriorityQueue<Node>()) }
repeat(m) {
val (start: Int, dest: Int, dist: Int) = readLine()
.split(" ")
.map { it.toInt() }
adjList[start - 1].add(Node(dest - 1, dist))
}
val resultList: MutableList<Int> = MutableList(n) { 0 }
for (i in 0 until n) {
resultList[i] += dijkstraMatrix(i, x - 1, n)
resultList[i] += dijkstraMatrix(x - 1, i, n)
}
println(resultList.max())
}
fun dijkstraMatrix(start: Int, dest: Int, vertex: Int): Int {
val queue: PriorityQueue<Node> = PriorityQueue()
var distance: IntArray = IntArray(vertex) { Int.MAX_VALUE }
var check: BooleanArray = BooleanArray(vertex) { false }
queue.add(Node(start, 0))
distance[start] = 0
while (queue.isNotEmpty()) {
val now = queue.poll().index
if (check[now]) continue
check[now] = true
for (node in adjList[now]) {
if (distance[node.index] > distance[now] + node.dist) {
distance[node.index] = distance[now] + node.dist
queue.add(Node(node.index, distance[node.index]))
}
}
}
return distance[dest]
}
문제 풀이3 (FloydWarshall)
import java.io.BufferedReader
import java.io.InputStreamReader
var route: Array<IntArray> = arrayOf()
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val (n: Int, m: Int, x: Int) = readLine()
.split(" ")
.map { it.toInt() }
route = Array(n) { IntArray(n) { Int.MAX_VALUE } }
repeat(m) {
val (start: Int, dest: Int, distance: Int) = readLine()
.split(" ")
.map { it.toInt() }
route[start - 1][dest - 1] = distance
}
for (i in 0 until n)
route[i][i] = 0
floydWarshall(n)
var result: Int = 0
for (i in 0 until n)
result = Math.max(result, route[i][x - 1] + route[x - 1][i])
println(result)
}
fun floydWarshall(n: Int) {
for (k in 0 until n) {
for (i in 0 until n) {
if (i == k) continue
if (route[i][k] == Int.MAX_VALUE) continue
for (j in 0 until n) {
if (i == j) continue
if (route[k][j] == Int.MAX_VALUE) continue
route[i][j] = Math.min(route[i][k] + route[k][j], route[i][j])
}
}
}
}
문제 풀이4 (Dijkstra - Adjacency Matrix)
import java.io.BufferedReader
import java.io.InputStreamReader
var matrix: Array<IntArray> = arrayOf()
var distance: IntArray = intArrayOf()
var check: BooleanArray = booleanArrayOf()
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val (n: Int, m: Int, x: Int) = readLine()
.split(" ")
.map { it.toInt() }
matrix = Array(n) { IntArray(n) { Int.MAX_VALUE } }
check = BooleanArray(n) { false }
repeat(m) {
val (start: Int, dest: Int, distance) = readLine()
.split(" ")
.map { it.toInt() }
matrix[start - 1][dest - 1] = distance
}
var route: Array<IntArray> = Array(n) { intArrayOf() }
for (i in 0 until n) {
distance = matrix[i]
route[i] = dijkstra(n, i)
check.fill(false)
}
var result: Int = 0
for (i in 0 until n) {
result = Math.max(route[i][x - 1] + route[x - 1][i], result)
}
println(result)
}
fun dijkstra(n: Int, start: Int): IntArray {
distance[start] = 0
check[start] = true
repeat(n - 1) {
var min = Int.MAX_VALUE
var min_index = 0
for (i in 0 until n) {
if (check[i]) continue
if (min > distance[i]) {
min = distance[i]
min_index = i
}
}
check[min_index] = true
for (next in 0 until n) {
if (matrix[min_index][next] == Int.MAX_VALUE || matrix[min_index][next] == 0) continue
if (distance[next] > distance[min_index] + matrix[min_index][next]) {
distance[next] = distance[min_index] + matrix[min_index][next]
}
}
}
return distance
}