[백준 3109번] [Kotlin] 빵집

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

3109번: 빵집

난이도 : 골드 2
태그 : 그래프 이론, 그리디 알고리즘, 그래프 탐색, 깊이 우선 탐색

 

 

설명

첫째 열에서 시작해 서로 교차하거나 중첩되지 않으면서 마지막 열로 가는 경로를 찾는 문제입니다.

1번 예제 같은 경우는 최대 두 가지 경로를 그릴 수 있습니다.

 

 

2번 예제 같은 경우는 아래와 같이 최대 5개의 경로(파이프 라인)이 있습니다.

 

파이프라인은 왼쪽에서 오른쪽 방향으로 놓을 수 있으며,

오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래 방향으로 놓을 수 있습니다.

그럼, 파이프의 최대 개수를 구하려면 어떻게 해야 할까요?

 

바로 위 그림들 처럼 DFS를 사용할 때, 우측 대각선 위 - 우측 - 우측 대각선 아래 순서로 파이프를 두는(방문하는) 것 입니다.

 

 

 

 

소스코드

var r = -1
var c = -1
var cnt = 0
lateinit var map: Array<Array<Char>>
lateinit var visited: Array<Array<Boolean>>

fun main() = with(System.`in`.bufferedReader()) {
    val rc = readLine().split(" ").map { it.toInt() }
    r = rc[0]
    c = rc[1]

    map = Array(r) {
        val line = readLine()
        Array(c) { line[it] }
    }
    visited = Array(r) { Array(c) { false } }

    repeat(r) {
        if (dfs(it, 0)) cnt++
    }

    println(cnt)
}

fun dfs(x: Int, y: Int): Boolean {
    if (y == c - 1) return true

    for (dx in -1..1) {
        val nx = x + dx
        val ny = y + 1

        if (nx !in 0 until r ||
            visited[nx][ny] ||
            map[nx][ny] == 'x'
        ) continue

        visited[nx][ny] = true
        if (dfs(nx, ny)) return true
    }
    return false
}

 

 

오른쪽으로 갈 수록 y(열)이 증가하고,

위로 갈수록 x가 감소, 아래로 갈수록 x가 증가합니다.

따라서, (x-1,y+1) -> (x, y+1) -> (x+1, y+1) 순으로 탐색을 진행하며,

만약 맨 끝에 도달할 수 있다면 true를 return하고,

끝내 맨 끝에 도달할 수 없었다면 false를 return 합니다 (dfs 메서드 맨 마지막줄)

 

이후 main()에서 모든 행의 0번째 열에서 dfs를 차례로 수행하며,

true를 반환하는 경우만 카운트를 하여 풀 수 있었습니다.

 

 

 

후기

DFS에 약간의 그리디가 섞인 듯한 문제였습니다.

DFS 너무 좋아.