[Kotlin, S2] 백준 21736번 헌내기는 친구가 필요해

출처: unsplash.com

 

헌내기는 친구가 필요해(21736번)

Silver 2

#그래프 이론 #그래프 탐색 #너비 우선 탐색 #깊이 우선 탐색

 

문제 내용

 

 

문제 접근

캠퍼스의 구조를 2차원 리스트의 구조로 띄운 다음에 방문 여부와 벽(X)인지 확인해 위치를 이동해 가면서 만나는 사람이 있는지 확인해 주면 된다.

문제의 예제 1을 예로 들어 보겠다.

3 5
OOOPO
OIOOX
OOOXP

현재 도연이의 위치가 I이기 때문에 시작 좌표를 I값이 있는 곳으로 지정을 해주어야 한다.

그리고 도연이는 위, 아래, 오른쪽, 왼쪽으로만 이동할 수 있기 때문에 각 방향으로 이동했을 때 그 위치로 이동할 수 있는지 확인해 주어야 한다.

이동할 수 있는 위치인지 확인하는 조건은 2가지를 써야 한다.

1. 한 번도 방문한 적 없는 위치인지?

2. 해당 위치가 벽(X)이 아닌지?

 

위 2가지의 조건을 모두 체크해 주어야 한다. 바로 Kotlin 코드로 확인해 보자.

 

<조건 1>

한 번도 방문하지 않은 위치인지 확인하려면, 캠퍼스와 동일한 크기를 가진 2차원 리스트인 visited를 따로 생성해서 도연이가 해당 위치로 이동했으면 캠퍼스의 위치와 동일한 위치의 visited값을 체크해 주면 된다.

도연이가 한 번도 방문하지 않은 위치여야 하므로 다음과 같이 나타낼 수 있다.

!visited[y][x]

 

<조건 2>

도연이가 이동하는 경로가 벽(X)인지 확인해 주는 조건이 필요하다. 코드로 나타내면 아래와 같이 나타낼 수 있다.

campus[y][x] != "X"

 

<조건 3>

위 조건 2개를 모두 만족했다면 이동할 수 있는 위치라는 뜻이다.

마지막으로 이제 이동하는 경로에 사람(P)이 있는지 확인해 주는 조건도 필요하다.

campus[y][x] == "P"

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

private var campus = arrayOf<List<String>>()
private var visited = arrayOf<BooleanArray>()
private var meetPersonCnt = 0

private val dx = listOf(-1, 1, 0, 0)
private val dy = listOf(0, 0, -1, 1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (h, w) = readLine().split(" ").map { it.toInt() }

    campus = Array(h) { List(w) { "" } }
    visited = Array(h) { BooleanArray(w) }

    var startPoint = listOf<Int>()
    for (i in 0 until h) {
        val map = readLine().map { it.toString() }
        campus[i] = map

        for (j in map.indices) {
            if (map[j] == "I") startPoint = listOf(i, j)
        }
    }

    bfs(startPoint[1], startPoint[0])

    if (meetPersonCnt == 0) println("TT")
    else println(meetPersonCnt)
}

private fun bfs(x: Int, y: Int) {
    for (i in dx.indices) {
        val mx = x + dx[i]
        val my = y + dy[i]

        if (mx in campus[0].indices && my in campus.indices) {
            if (!visited[my][mx] && campus[my][mx] != "X") {
                visited[my][mx] = true
                if (campus[my][mx] == "P") meetPersonCnt++
                bfs(mx, my)
            }
        }
    }
}

 

문제 풀이

캠퍼스 그래프와 캠퍼스와 동일한 크기를 가진 방문 여부를 확인할 2차원 리스트를 만들어 준다.

처음에 캠퍼스에 값을 입력받을 때, 입력받는 값이 I인지 확인해서 따로 변수에 저장한다. 시작 지점으로 사용해야 한다.

 

캠퍼스에 값이 모두 들어가면 bfs(깊이 우선 탐색 함수)를 수행한다.

코드 상단에 이동 위치를 저장할 변수 dx, dy를 생성해 주었다. 위 변수 2개로 위치를 이동할 수 있다.

이동한 위치가 캠퍼스 범위를 벗어나는지 확인하고, 조건 1과 조건 2를 만족할 때만 조건 3을 수행한다.

조건 3이 만족하지 않아도 재귀 호출을 해야 한다. 일단 그래프는 다 순회를 해주어야 하기 때문이다.

조건 3이 만족한다면 사람을 만난 경우이기 때문에 카운트를 늘려 준다.

그리고 방문 여부 그래프에 표시를 해주는 것도 잊지 말자.

 

함수가 종료된 후, 만난 사람이 없으면 TT를 출력하고 아니면 만난 사람의 수를 출력한다.

 

 

문제 해결 과정

기초적인 그래프 탐색 문제이다.

그래프 탐색 기초 문제는 실버 2부터 시작하는 듯하다.

그래프 탐색 알고리즘을 다룰 줄 아는 나에게는 매우 쉬운 문제였다. 아직은 그래프 탐색 활용이 가능한 경지는 아니다.