백준 3190 뱀

출처: https://www.acmicpc.net/problem/3190

분류: 자료구조

---

접근방식

특별한 알고리즘이나 수학적 개념보다 주어진 상황에 충실히 구현하면 되는 문제였습니다.

2차원 배열 맵을 만들어두고 체크해도 되겠으나(많이들 그런 식으로 푸신 것 같더라구요) 저는 굳이 배열을 따로 만들진 않고 범위만 체크했습니다. 

 

해결방법

뱀을 링크드리스트 형태로 구현해줬고 body set을 정의해서 자기 자신으로 가려고 하는지 확인했습니다. enum, class 등등으로 정의해서 좀 느리고 길게 풀어진 것 같긴 하지만 그래도 나름 swift스럽게(?) 푼 것 같기는 합니다. 

사과를 찾았으면 해당 사과를 지워줘야 하는데 이걸 빼먹어서 시간을 좀 잡아먹었네요 ;; 
혹시나 저처럼 실수하시는 분들이 없기를 ㅠㅠ

enum Cmd: String {
    case L = "L"
    case D = "D"
}

enum Direction {
    case up
    case down
    case left
    case right
    
    func rotate(order: Cmd) -> Direction {
        switch self {
            case .up: return order == .L ? .left : .right
            case .down: return order == .L ? .right : .left
            case .left: return order == .L ? .down : .up
            case .right: return order == .L ? .up : .down
        }
    }
    
    func next(from curr: Point) -> Point {
        switch self {
            case .up: return Point(curr.r-1, curr.c)
            case .down: return Point(curr.r+1, curr.c)
            case .left: return Point(curr.r, curr.c-1)
            case .right: return Point(curr.r, curr.c+1)
        }
    }
}

class Point: Hashable, CustomStringConvertible {
    var r: Int
    var c: Int
    var next: Point?
    weak var previous: Point?
    
    init(_ r: Int, _ c: Int) {
        self.r = r
        self.c = c
    }
    
    static func ==(lhs: Point, rhs: Point) -> Bool {
        return lhs.r == rhs.r && lhs.c == rhs.c
    }
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(r)
        hasher.combine(c)
    }
    
    var description: String {
        return "(\(r),\(c))"
    }
}

class Snake {
    var head: Point
    var tail: Point
    private(set) var body: Set<Point>
    
    init(_ point: Point) {
        head = point
        tail = point
        body = Set<Point>(arrayLiteral: point)
    }
    
    func move(to next: Point, findApple: Bool) {
        body.insert(next)
        head.next = next
        next.previous = head
        head = next
        
        if !findApple {
            body.remove(tail)
            tail = tail.next!
            tail.previous?.next = nil
            tail.previous = nil
        }
    }
}

typealias Order = (duetime: Int, command: Cmd)

var n = Int(readLine()!)!

var k = Int(readLine()!)!
var applePoints = Set<Point>((0..<k).map({ _ -> Point in
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    return Point(input[0]-1, input[1]-1)
}))

var l = Int(readLine()!)!
var orders: [Order] = (0..<l).map { _ in
    let input = readLine()!.split(separator: " ").map { String($0) }
    return Order(Int(input[0])!, Cmd(rawValue: input[1])!)
}.reversed()

func isInRange(_ curr: Point) -> Bool {
    return 0..<n ~= curr.r && 0..<n ~= curr.c
}

func solution() {
    var runningTime = 0
    let snake = Snake(Point(0, 0))
    var dir = Direction.right
    var order = orders.popLast()

    while true {
        runningTime += 1
        let next = dir.next(from: snake.head)
        guard isInRange(next), !snake.body.contains(next) else { break }
        snake.move(to: next, findApple: applePoints.contains(next))
        applePoints.remove(next)
        
        while let currentOrder = order, currentOrder.duetime == runningTime {
            dir = dir.rotate(order: currentOrder.command)
            order = orders.popLast()
        }
    }
    print(runningTime)
}

solution()

배운점

넘 느리다... 연습 또 연습 🔥

 

오답원인

만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.

문제를 잘 읽자.

 

회고