[백준/BOJ] 1189번: 컴백홈

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

1189번: 컴백홈

문제

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

해설

출발하는 위치는 (r-1, 0)이고, 도착해야하는 위치는 (0, c-1)이다.

T인 경우는 갈 수 없는 길이고, 이미 지나간 길로도 갈 수 없다.

한 지점을 방문했다면 dfs를 통해 다음 지점으로 가게 되며 원래의 길을 방문했던 흔적을 없앤다.

dfs를 하며 방문횟수가 k와 같고, 현재 지점이 도착 지점이라면 return을 해준다.

소스 코드

import java.util.*

lateinit var count: Array<IntArray>
lateinit var map: Array<CharArray>
var dx = arrayOf(-1, 1, 0, 0)
var dy = arrayOf(0, 0, -1, 1)
var r = 0
var c = 0
var k = 0
var result = 0

fun main() = with(System.`in`.bufferedReader()) {
    val st = StringTokenizer(readLine())
    r = st.nextToken().toInt()
    c = st.nextToken().toInt()
    k = st.nextToken().toInt()
    map = Array(r) { CharArray(c) { '.' } }
    count = Array(r) { IntArray(c) { 0 } }
    count[r-1][0] = 1
    for(i in 0 until r) {
        val possible = readLine()
        for(j in 0 until c) {
            map[i][j] = possible[j]
        }
    }
    goHome(r-1, 0, 1)
    println(result)
}

fun goHome(y: Int, x: Int, cnt: Int) {
    if(cnt == k && y == 0 && x == c - 1) {
        result++
        return
    }
    repeat(4) { i ->
        var nx = x + dx[i]
        var ny = y + dy[i]
        if(nx >= 0 && ny >= 0 && nx < c && ny < r) {
            if(map[ny][nx] == '.') {
                if(count[ny][nx] == 0) {
                    count[ny][nx] = 1
                    goHome(ny, nx, cnt + 1)
                    count[ny][nx] = 0
                }
            }
        }
    }
}