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

2024. 6. 5. 12:20· → Problems
목차
  1. 문제 소개
  2. 문제 풀이
  3. 초기 문제풀이 (시간초과)
  4. 문제풀이 (정답)

문제 소개

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

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)

'→ Problems' 카테고리의 다른 글

[Algorithm] 백준 - 16928번 뱀과 사다리 게임 (Swift)  (0) 2024.06.07
[Algorithm] 백준 - 1062번 가르침 (Swift)  (1) 2024.06.06
[Algorithm] 백준 - 2580번 스도쿠 (Swift)  (0) 2024.06.04
[Algorithm] 백준 - 9663번 N-Queen (Swift)  (0) 2024.06.03
[Algorithm] 백준 - 1080번 행렬 (Swift)  (0) 2024.06.02
  1. 문제 소개
  2. 문제 풀이
  3. 초기 문제풀이 (시간초과)
  4. 문제풀이 (정답)
'→ Problems' 카테고리의 다른 글
  • [Algorithm] 백준 - 16928번 뱀과 사다리 게임 (Swift)
  • [Algorithm] 백준 - 1062번 가르침 (Swift)
  • [Algorithm] 백준 - 2580번 스도쿠 (Swift)
  • [Algorithm] 백준 - 9663번 N-Queen (Swift)
Swift librarian
Swift librarian
Swift librarian
Swift Library
Swift librarian
전체
오늘
어제
  • 분류 전체보기 (231)
    • 📺 Programming (5)
    • → Architecture (2)
    • → Design Pattern (0)
    • → Computer Science (15)
    • ⚙️ Algorithm (0)
    • → 알고리즘 관련 (22)
    • → Problems (104)
    • 🚀 Project (0)
    • → 알쏭달쏭 (0)
    • → Shook (2)
    • → Solver (8)
    • → Taster (7)
    • → Outline (4)
    • → Pointer (2)
    • → Guesser (3)
    • 🦜 Swift (2)
    • → Swift Archive (12)
    • → Swift Study (12)
    • → Xcode (6)
    • 🧰 Framework (0)
    • → Foundation (1)
    • → UIKit (2)
    • → SwiftUI (3)
    • → CoreData (2)
    • → MapKit (1)
    • → CoreHaptic (1)
    • → User Notification (1)
    • → StoreKit (2)
    • 🏛️ Library (0)
    • → TCA (0)
    • 🐈‍⬛ Git (8)
    • → Git의 원리 (2)
    • → Git 심화 (1)
    • 📦 Other (1)
    • 👦🏻 Log (0)

최근 글

hELLO · Designed By 정상우.v4.2.2
Swift librarian
[Algorithm] 백준 - 1987번 알파벳 (Swift) (비트마스크)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.