백준 17070 파이프 옮기기 1

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

분류: DP, 백트래킹

---

접근방식

주어진 요구사항 대로 파이프의 이동 가능 위치를 잘 계산하고 나면 백트래킹으로 도착한 경우의 수를 세주면 되는 문제였습니다.

파이프의 끝 점에서 출발한 경로는 역시 다시 방문해줄 필요가 없으므로 방향을 고려한 3차원 배열에 이를 기록해서 방문 횟수를 줄여줬습니다.

조금 귀찮긴 하지만 크게 어렵지는 않아서 풀이를 보시면 이해가 되실거에요 :)

 

해결방법

let n = Int(readLine()!)!
var map = [[Int]]()
for _ in 0..<n {
    map.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

enum Direction: Int {
    case horizontal = 0
    case vertical
    case diagonal
}
typealias Point = (r: Int, c: Int)
typealias Pipe = (Point, Point)

func direction(_ pipe: Pipe) -> Direction {
    if pipe.0.r == pipe.1.r, abs(pipe.0.c - pipe.1.c) == 1 {
        return .horizontal
    } else if pipe.0.c == pipe.1.c, abs(pipe.0.r - pipe.1.r) == 1 {
        return .vertical
    } else {
        return .diagonal
    }
}

func next(_ pipe: Pipe) -> [Pipe] {
    var nextPipes = [Pipe]()
    let dir = direction(pipe)
    
    if dir == .horizontal || dir == .diagonal {
        if 0..<n ~= pipe.1.c+1, map[pipe.1.r][pipe.1.c+1] != 1 {
            nextPipes.append(Pipe(pipe.1, (pipe.1.r, pipe.1.c+1)))
        }
    }
    
    if dir == .vertical || dir == .diagonal {
        if 0..<n ~= pipe.1.r+1, map[pipe.1.r+1][pipe.1.c] != 1 {
            nextPipes.append(Pipe(pipe.1, (pipe.1.r+1, pipe.1.c)))
        }
    }
    
    if 0..<n ~= pipe.1.r+1, 0..<n ~= pipe.1.c+1,
       map[pipe.1.r+1][pipe.1.c] != 1,
       map[pipe.1.r][pipe.1.c+1] != 1,
       map[pipe.1.r+1][pipe.1.c+1] != 1 {
        nextPipes.append(Pipe(pipe.1, (pipe.1.r+1, pipe.1.c+1)))
    }
    
    return nextPipes
}

var dpMap = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: -1, count: 3), count: n), count: n)

func move(_ pipe: Pipe) -> Int {
    let dir = direction(pipe).rawValue
    guard dpMap[pipe.1.r][pipe.1.c][dir] == -1 else { return dpMap[pipe.1.r][pipe.1.c][dir] }
    dpMap[pipe.1.r][pipe.1.c][dir] = 0
    
    if pipe.1.r == n-1, pipe.1.c == n-1 {
        dpMap[pipe.1.r][pipe.1.c][dir] = 1
        return dpMap[pipe.1.r][pipe.1.c][dir]
    }
    
    for p in next(pipe) {
        dpMap[pipe.1.r][pipe.1.c][dir] += move(p)
    }
    
    return dpMap[pipe.1.r][pipe.1.c][dir]
}

print(move(((0,0), (0,1))))

 

배운점