BOJ-1987 알파벳 Swift

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

내가 푼 풀이

- 문제의 원리는 어렵지않았다.

- (0, 0)에서 시작하여 해당 지점 알파벳이 중복되지않게 최대로 가는 경우의 수를 구하는데 백트래킹이 생각났다.

- 한 쪽으로 알파벳이 중복되지 않을만큼 이동했다가, 중복이된다면 이전 기점으로 돌아와 재탐색한다.

- 처음에는 배열의크기가 최대 20 * 20 이라 단순히 DFS 백트래킹 방식으로 풀면 되겠다 했는데 시간초과가 떴다.

- 탐색하면서 넣는 배열을 확인하는 contains 함수의 시간복잡도가 O(N)이라 여기서 문제인듯 했다.

- Dictionary를 26크기만큼 선언해 알파벳을 만나면 값을 1로 변경하여 중복을 확인하는 방법을 2차로 사용했지만, 이것도 역시 시간초과가 떴다.

- 여기서 더이상 줄일 방법이 떠오르지 않아서 다른 분들이 푼 풀이를 참고했다.

- 백트래킹 DFS 로 푸는방법은 맞았지만, Swift는 시간제한이 빡빡해서 비트마스킹을 사용했다.

- A : 0, B: 1 ... Z: 25 로 지정하고, 알파벳을 만나면 쉬프트 연산자를 이용하여 비트에 넣어준다.

- 다음 알파벳을 비트에 넣은 후 AND 연산을 해서 0이되면, 중복되지 않은 알파벳이고, 0이 아니면 중복된 알파벳으로 판단한다.

- 배열과 딕셔너리를 이용하여 중복알파벳을 판단했는데, 정수 하나로 판단하니 시간이 확 줄어들었다.

- 비트마스킹 기억해두도록 하자.

 

import Foundation

let input = readLine()!.split(separator: " ").map{ Int($0)! }
let r = input[0]
let c = input[1]
var arr = [[Int]]()
var result = 0
let dx = [0,1,0,-1]
let dy = [1,0,-1,0]

// 알파벳 비트마스킹
for i in 0..<r {
    arr.append(readLine()!.map{ Int($0.asciiValue!) - 65 })
}

// DFS 백트래킹
func dfs(x: Int, y: Int, count: Int, alphabet: Int) {
    result = max(result, count)

    for i in 0..<4 {
        let mx = dx[i] + x
        let my = dy[i] + y

        if (mx >= 0 && mx < r) && (my >= 0 && my < c) && (alphabet & 1 << arr[mx][my] == 0) {
            dfs(x: mx, y: my, count: count+1, alphabet: alphabet | 1 << arr[mx][my])
            
        }
    }

}

dfs(x: 0, y: 0, count: 1, alphabet: 1 << arr[0][0])
print(result)