백준 2210 숫자판 점프

출처: www.acmicpc.net/problem/2210

분류: dfs, 완전탐색

---

접근방식

왔던 칸을 다시 가도 되므로 그냥 보드의 범위를 넘지 않는지만 체크하면서

6자리까지 dfs 로 계속 숫자를 더해주고 set에 담아서 개수를 출력하면 되는 문제였습니다.

저는 다음 칸을 만들고 filter로 범위를 걸러주는 식으로 풀어서 먼저 범위를 체크하고 만드는 것보다 시간이 좀 더 걸린 것 같네요!

 

해결방법

typealias Point = (r: Int, c: Int)

var board = [[String]]()
var digitSet = Set<String>()

for _ in 0..<5 {
    board.append(readLine()!.split(separator: " ").map { String($0) })
}

func nexts(_ p: Point) -> [Point] {
    return [
        (p.r+1, p.c),
        (p.r-1, p.c),
        (p.r, p.c+1),
        (p.r, p.c-1)
    ].filter { 0..<5 ~= $0.r && 0..<5 ~= $0.c }
}

func jump(_ p: Point, _ digit: String) {
    guard digit.count < 6 else {
        digitSet.insert(digit)
        return
    }
    
    for next in nexts(p) {
        jump(next, digit + board[p.r][p.c])
    }
}

for r in 0..<5 {
    for c in 0..<5 {
        jump((r, c), "")
    }
}

print(digitSet.count)