백준 - 11403 경로 찾기(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/11403

 

[접근 방법]

그냥 간단하게 BFS로 시작해서 탐색하면 된다.

단, 시작점으로 돌아오는 사이클을 예외처리해야 한다.

일반적으로 BFS로 너비탐색을 하는 경우, 시작점을 방문 처리한다.

이런 식으로 처리할 경우, 자기 자신은 무조건 방문할 수 있는 것으로 판단하여 n행 n열은 무조건 방문 처리 된다.

따라서, 이를 예외 처리해야 한다.

 

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.LinkedList

val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main() {
    val n = br.readLine().toInt()
    val map = Array(n) { LinkedList<Int>() }

    repeat(n) {
        val line = br.readLine().split(" ").map { it.toInt() }
        line.forEachIndexed {idx, x ->
            if (x == 1) {
                map[it].add(idx)
            }
        }
    }

    for (start in 0 until n) {
        bfs(start, map)
    }
    bw.flush()
}

fun bfs(startPoint: Int, map: Array<LinkedList<Int>>) {
    val visited = BooleanArray(map.size)
    val queue = LinkedList<Int>()

    var isCycle = false
    queue.offer(startPoint)
    while (queue.isNotEmpty()) {
        val node = queue.poll()
        visited[node] = true

        for (next in map[node]) {
            // 시작지점이면 체크하고 큐에 넣지는 않음.
            if (next == startPoint) {
                isCycle = true
                continue
            }

            if (visited[next]) {
                continue
            }

            visited[next] = true
            queue.offer(next)
        }
    }

    for (i in visited.indices) {
        if (i == startPoint) {
            if (isCycle) {
                bw.write("1")
            } else {
                bw.write("0")
            }
            bw.write(" ")
            continue
        }

        if (visited[i]) {
            bw.write("1")
        } else {
            bw.write("0")
        }
        bw.write(" ")
    }

    bw.write("\n")
}