[Algorithm] 백준 - 1987번 알파벳 (Swift) (비트마스크)

문제 소개

문제 자체는 아주 간단했다. 아래의 입력값이 주어진다면 알파벳이 중복되지 않게 이동하는 최대 거리를 구하는 문제였다.

2 4
CAAB
ADCB

// 정답 3

 

문제 풀이

초기 문제풀이 (시간초과)

우선 최대한 지날 수 있는 칸이기 때문에 dfs를 생각했고, 백트래킹을 통해 문제를 해결하면 된다고 생각했다. 그리고 알파벳을 어떻게 저장할까 고민했는데 Dictionary 나 Set 으로 저장하면 O(1) 으로 알파벳을 방문했는지 빠르게 알 수 있기 때문에 나는 이중에 Dictionary 를 활용했다,

import Foundation

let rc = readLine()!.split(separator: " ").map { Int($0)! }
let (r, c) = (rc[0], rc[1])
let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
var map = [[String]]()
var visited = [String: Bool]()

for _ in 0..<r {
    let input = Array(readLine()!).map { String($0) }
    map.append(input)
}

var count = 0

func dfs(_ i: Int, _ j: Int, _ depth: Int) {    
    count = max(count, depth)
    
    for direction in directions {
        let k = i + direction.0
        let l = j + direction.1
        
        if k >= 0 && k < r && l >= 0 && l < c {
            let next = map[k][l]
            
            if visited[next] != true {
                visited[next] = true
                dfs(k, l, depth + 1)
                visited[next] = false
            }
        }
    }
}

let first = map[0][0]
visited[first] = true
dfs(0, 0, 1)

print(count)

 
문제는 이렇게 푸니 반례들은 다 맞는데, 시간초과가 발생하는 것이었다. 로직에는 문제가 없었고, 많은 java, python에서는 이 방식으로도 많이 해결이 되는 모양이었다... Swift... 그래서 어떻게 하면 빠르게 알파벳 방문을 판별할 수 있을까? 고민하게 되었다.
 

문제풀이 (정답)

바로 비트마스크를 활용하여 푸는 방법이었다. 아이디어는 다음과 같다. A를 0으로 둔다면 아래와 같이 비트마스킹이 가능하다.

// A 인 경우
let bitmaskA = 1 << 0 // 0001

// B 인 경우
let bitmaskB = 1 << 1 // 0010

// C 인 경우
let bitmaskC = 1 << 2 // 0100

// << : 왼쪽으로 시프트
// >> : 오른쪽으로 시프트

 
이렇게 비트마스크를 한 뒤 방문한 곳을 아래와 같이 저장해준다.

// 1010 즉, 10 이면 B, D 를 방문한 것

 
그리고 & 연산을 통해 새로운 알파벳인지 확인한다. 그리고 다음 비트마스크에는 | 연산을 통해 방문 체크를 해준다.

let newBitmask = 1 << map[k][l]
            
if bitmask & newBitmask == 0 {
    dfs(k, l, depth+1, bitmask | newBitmask)
}

// &(AND) 연산 : 두 비트가 모두 1 일때 1
// |(OR) 연산 : 두 비트중 하나가 1 일때 1
// ^(XOR) 연산 : 두 비트가 다를때 1
// ~(NOT) 연산 : 비트의 모든 자리를 반전

 

최종 코드

이렇게 알파벳 배열 같은 간단한 배열은 visited로 체크하는 것보다 비트마스크를 통해 Int 형식으로 전달하는 방법이 훨씬 효율적이라는 것을 알게 되었다.

import Foundation

let rc = readLine()!.split(separator: " ").map { Int($0)! }
let (r, c) = (rc[0], rc[1])
let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
var map = [[Int]]()

for _ in 0..<r {
    let input = readLine()!.map { Int($0.asciiValue ?? 65) - 65 }
    map.append(input)
}

var count = 0

func dfs(_ i: Int, _ j: Int, _ depth: Int, _ bitmask: Int) {
    count = max(count, depth)
    
    for direction in directions {
        let k = i + direction.0
        let l = j + direction.1
        
        if k >= 0 && k < r && l >= 0 && l < c {
            let newBitmask = 1 << map[k][l]
            
            if bitmask & newBitmask == 0 {
                dfs(k, l, depth+1, bitmask | newBitmask)
            }
        }
    }
}

let first = map[0][0]
dfs(0, 0, 1, 1 << map[0][0])

print(count)