1189번: 컴백홈

문제 풀이 아이디어

이 문제는 전형적인 bfs 문제처럼 생겼습니다. 하지만 어디에도 최단거리라는 조건은 없습니다. 단지 왔던 길을 다시 가지 않고 거리가 K인 길만 찾으면 됩니다.

따라서 최단거리에 연연하지 않고 모든 목적지까지 가는 경우의 수를 따져서 거리가 K인 경우만 찾으면 됩니다.

즉 dfs나 bfs에 관계 없이 어떤 완전탐색 알고리즘으로도 풀 수 있습니다. 여기서는 dfs로 풀어보겠습니다.

코드

// 해당 좌표가 갈 수 있는 좌표인지 알아보는 함수
func isValid(_ r: Int, _ c: Int) -> Bool {
    r >= 0 && r < R && c >= 0 && c < C && matrix[r][c] != "T"
}

// 동서남북 좌표 변화
let dr = [1, -1, 0, 0]
let dc = [0, 0, 1, -1]

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (R, C, K) = (input[0], input[1], input[2])

// 지도 입력 받기
var matrix = [[String]]()
for _ in 0..<R {
    matrix.append(readLine()!.map { String($0) })
}

// 거리가 K인 경우
var cnt = 0

// 방문 체크 배열
var visited = Array(repeating: Array(repeating: false, count: C), count: R)

// dfs 구현
func dfs(_ r: Int, _ c: Int, _ d: Int) {
    // 목적지에 도착하면
    if r == 0 && c == C - 1 {
        if d == K { //👉 거리가 K일 때만 cnt + 1
            cnt += 1
        }
        return
    }
    
    // 동서남북 완전 탐색
    for i in 0..<4 {
        let nr = r + dr[i]
        let nc = c + dc[i]
        if isValid(nr, nc) && !visited[nr][nc] {
            visited[nr][nc] = true
            dfs(nr, nc, d + 1)
            visited[nr][nc] = false
        }
    }
}

//❗️ 동서남북 문제 dfs로 풀 때는
    // bfs와는 다르게 함수 밖에서 출발점의 방문체크를 해준다! (내부에서 방문체크를 하지 못하기 때문)
visited[R - 1][0] = true
dfs(R - 1, 0, 1)
print(cnt)