만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 1194 달이 차오른다, 가자.

13 Dec 2021

문제 보러 가기

재미있었던 문제, 일반적인 BFS 문제에 비트마스크를 섞은 문제이다. 메모리 제한이 꽤 제한적인 편이여서 메모리적으로 고려를 하면서 풀면 좋다.

방식은 A-F 까지의 키를 각각 1, 2, 4, 8, 16, 32에 대응시킨 뒤 해당 키를 비트마스크 연산으로 관리해주는 문제이다. 이 때 비트마스크 연산을 이용한다면 A-F까지의 키를 단순히 Int값 0부터 63으로 관리할 수 있게된다. 예를들어 Key = 63이면 A-F의 키를 모두 들고있는 셈이 된다. 또 Key = 33이면 A키와 F키만 들고있다는 의미가 된다.

먼저 미로를 단순히 NxM 한개만 존재하는 것이 아니라 Key값에 따라 개별적인 미로를 갖는다고 생각하자. 예를들어 Key 0일때 통과했던 곳이여도 Key값이 바뀌면 통과한적이 없는것과 마찬가지로 보는 것이다. 따라서 NxMx64의 방문여부 Check 배열이 존재하게 된다. 그 후 BFS를 이용하여 방문하지 않은 곳일 경우 Queue에 추가해주면서 출구를 찾을때까지 혹은 Queue가 끝날때까지 반복해주면 된다.

이 때 메모리적으로 조건이 있기 때문에 Queue에 추가하기전에 출구 여부를 판단해서 출구를 찾을 경우 더이상 작업을 하지 않도록 관리해준다. 또한 동일한 위치를 동일한 키로 방문하는 경우를 중복해서 Queue에 추가하는 일이 없도록 Queue에 새로운 위치를 추가하게 되면 해당 위치&Key에 해당하는 Check 배열을 항상 True로 만들어주자.

또한 시간적 조건을 통과하기 위해서 Queue.removeFirst()를 사용하지 말고 Queue에 계속 추가하면서 index를 관리해주는 방식으로 접근하는 것이 좋다. (필자는 처음에 removeFirst를 써서 시간초과가 났다…)

//
//  main.swift
//  baekjoon
//
//  Created by 강현준 on 2021/12/13.
//

import Foundation

enum Key: Int {
    case a, b, c, d, e, f
    
    static func bitmaskKey(of key: Character) -> Int {
        switch key {
        case "a": return 1
        case "b": return 2
        case "c": return 4
        case "d": return 8
        case "e": return 16
        case "f": return 32
        default: return 0
        }
    }
    
    static func isPassable(road: Character, key: Int) -> Bool {
        switch road {
        case "A": return key&1 == 1
        case "B": return key&2 == 2
        case "C": return key&4 == 4
        case "D": return key&8 == 8
        case "E": return key&16 == 16
        case "F": return key&32 == 32
        case "#": return false
        default: return true
        }
    }
}

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nm[0]
let m = nm[1]
var board: [[Character]] = []
var startX = -1
var startY = -1

(0..<n).forEach { _ in board.append(readLine()!.map { Character(String($0)) }) }
loop: for i in 0..<n {
    for j in 0..<m {
        if board[i][j] == "0" {
            startX = j
            startY = i
            break loop
        }
    }
}

let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]
var boardChecker = Array(repeating: Array(repeating: Array(repeating: false, count: m), count: n), count: 64)
var queue = [(y: Int, x: Int, key: Int)]()
queue.append((startY, startX, 0))
boardChecker[0][startY][startX] = true

var index = 0
var result = 0
var flag = false
loop: while index < queue.count {
    result += 1
    for k in index..<queue.count {
        let position = queue[k]
        for i in 0...3 {
            let nextY = position.y + dy[i]
            let nextX = position.x + dx[i]
            if (0..<n) ~= nextY && (0..<m) ~= nextX && !boardChecker[position.key][nextY][nextX] &&
                Key.isPassable(road: board[nextY][nextX], key: position.key) {
                
                if board[nextY][nextX] == "1" {
                    flag = true
                    break loop
                }
                let newKey = position.key|Key.bitmaskKey(of: board[nextY][nextX])
                boardChecker[newKey][nextY][nextX] = true
                queue.append((nextY, nextX, newKey))
            }
        }
        index += 1
    }
}
print(flag ? result : -1)

Related posts