백준 3109 빵집

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

맨 왼쪽 열에서 오른쪽 열로 연결되는 파이프를 설치하는 문제이다.

파이프는 겹치거나 접할 수 없으며, 오른쪽 or 오른쪽 위 or 오른쪽 아래 방향으로만 연결할 수 있다.

이러한 예시가 주어진다고 하면 최대로 파이프를 연결한다면 아래처럼 된다.

최대 2개의 파이프라인을 설치할 수 있다.

R(행 개수)이 최대 10,000이고 C(열 개수)가 최대 500이므로 직접 모든 케이스를 확인하는 것은 어렵다 생각했다.

어떻게 풀어야할지 감이 안왔는데 문제 카테고리가 그리디에 있기에 생각해보다가 맨 왼쪽 열의 위에서부터 가능한 한 오른쪽 위로 파이프를 설치해 보면 어떨까 생각하였다.

풀이 과정은 다음과 같다.

1. dfs 함수 및 방문 체크를 위한 visited를 정의한다
   시작 위치부터 오른쪽 위 - 오른쪽 - 오른쪽 아래 순서로 탐색한다.
   맨 오른쪽 열에 도착하면 flag를 통해 해당 위치에선 더이상 탐색하지 않는다.

2. 맨 왼쪽 열에 대해 위에서부터 dfs함수를 호출한다.

3. 맨 오른쪽 열에 도착한 케이스의 개수를 출력한다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
   val (R, C) = readLine().split(' ').map{it.toInt()}

    val field = Array(R){ readLine().toCharArray() }

    val visited = Array(R){BooleanArray(C){false} }

    var ans = 0
    var find = false
    fun dfs(r: Int, c: Int){
        if(find || visited[r][c] || field[r][c] == 'x') return
        visited[r][c] = true
        if(c == C - 1){
            ans++
            find = true
            return
        }

        for(i in -1..1){
            if(isInside(r + i, c + 1, R, C) && !visited[r + i][c + 1]){
                dfs(r + i, c + 1)
            }
        }
    }

    for(i in visited.indices){
        find = false
        dfs(i, 0)
    }

    print(ans)
}

fun isInside(r: Int, c: Int, R: Int, C: Int) = r in 0 until R && c in 0 until C

통과는 했지만 파이프를 최대한 오른쪽 위로 설치하는 방법이 정말 올바른지 확실한 검증은 하지 못했다.

시간날 때 해당 방법이 파이프라인 최대 개수를 보장하는 이유를 생각해 봐야겠다.