[백준 16197] 두 동전 (Swift)

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

 

DFS BFS

아래와 같은 보드에 #은 벽, . 은 빈칸, o는 동전이다. 동전은 2개만 존재함

6 2
.#
.#
.#
o#
o#
##

네 방향키를 누를 수 있고, 누를 때 마다 두 동전이 그 방향으로 한칸씩 동시에 이동한다. 

벽이 있는 칸으로는 이동할 수 없음 (단 이동 카운트는 체크) 이동하려는 칸에 다른 동전이 있어도 이동할 수 있음

 

이때, 두 동전 중 하나만 떨어지는 최소 횟수를 출력하는 문제, 단, 10번 보다 버튼을 더 많이 눌러야 하거나 두 동전을 떨어뜨릴 수 없는 경우 -1을 출력한다.

 

접근방법

BFS를 곁들인..DFS식으로 구현하되 모든 경우를 고려하는게 관건이었던 문제였다.

dfs 함수 인자로 두 동전의 현 위치와 현재까지 누른 버튼 횟수를 넘긴다.

그리고 dfs 초입에서

두 동전 중 하나만 떨어졌을 경우, 지금까지 누른 버튼 횟수를 현재까지의 최소 버튼 누른 횟수와 비교하여 적은 값이면 갱신한다.

두 동전 모두 떨어졌을 경우 dfs 함수 종료

두 동전 모두 보드에 남아있을 경우 이동을 계속한다. 다만 10번을 이미 이동했을 경우 종료한다.

두 동전 모두 방향키 마다 한칸씩 이동하되, 이동하려는 칸이 벽이면 이동하지 않는다.

그렇게 다음 동전 위치를 담은 좌표와 1 증가한 버튼 누른 횟수를 dfs함수에 넘기면서 호출한다.

 

소스코드

import Foundation

func solution() -> Int {
    
    let NM:[Int] = (readLine()?.split(separator: " ").map{Int($0)!})!
    let N = NM[0]
    let M = NM[1]
    
    var map:[[Character]] = []
    for r in 0..<N {
        let line:[Character] = Array(readLine()!)
        map.append(line)
    }
    
    var coins:[(Int, Int)] = []
    for r in 0..<N {
        for c in 0..<M {
            if map[r][c] == "o" {
                coins.append((r,c))
            }
        }
    }
    
    var result = 11
    let dr = [-1,1,0,0]
    let dc = [0,0,-1,1]
    
    func dfs(_ a:(Int, Int), _ b:(Int, Int), _ cnt:Int) {
        // 떨어진지 체크
        let aisfallen = !(a.0 >= 0 && a.0 < N && a.1 >= 0 && a.1 < M)
        let bisfallen = !(b.0 >= 0 && b.0 < N && b.1 >= 0 && b.1 < M)
        if (aisfallen && !bisfallen) || (!aisfallen && bisfallen) {
            // 둘중 하나만 떨어짐
            result = min(result, cnt)
        } else if !aisfallen && !bisfallen {
            // 둘 다 안떨어짐
            if cnt >= 10 {
                return
            }
            for i in 0..<4 {
                var nar = a.0 + dr[i]
                var nac = a.1 + dc[i]
                var nbr = b.0 + dr[i]
                var nbc = b.1 + dc[i]
                
                if nar >= 0 && nar < N && nac >= 0 && nac < M {
                    if map[nar][nac] == "#" {
                        nar = a.0
                        nac = a.1
                    }
                }
                if nbr >= 0 && nbr < N && nbc >= 0 && nbc < M {
                    if map[nbr][nbc] == "#" {
                        nbr = b.0
                        nbc = b.1
                    }
                }
                dfs((nar, nac), (nbr, nbc), cnt+1)
            }
        } else {
            // 둘 다 떨어짐
            // 종료
        }
    }
    
    dfs(coins[0], coins[1], 0)
    
    if result == 11 {
        result = -1
    }
    
    return result
}

print(solution())

효율적인 코드인지는 모르겠지만.. N,M이 20으로 작고, 버튼 횟수가 10로 제한되어 있어서 맘편히 풂..