백준 1987번 알파벳 - SWIFT

문제

---

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

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

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

 

입력

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

 

출력

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

 

문제 링크

1987번: 알파벳

 

 

풀이

---

전형적인 DFS문제이다.

 

밟은 알파벳들을 방문했다고 체크해주고, 방문하지 않은 타일을 선택해서 계속 나아가면 된다.

기본적으로 재귀를 쓰고, 상, 하, 좌,우의 네 방향을 검사하다보니 다음에 실행될 함수의 갯수가 많으면 세 배씩 늘어난다.

그래도 20 * 20 크기에 알파벳은 26개 까지밖에 없으므로 전체 계산은 1억을 초과하진 않을 것이라고 본다.

하지만 Swift에서는 시간을 더 줄여야한다.

위의 방법을 날 것으로 사용했더니, 시간초과로 실패했다.

먼저 시간초과가 발생한 풀이 방식부터 보자.

 

실패한 풀이 1: Set 컬렉션 사용

`Set`을 사용한 이유는 `Set`의 `contains()` 메소드의 시간 복잡도는 `O(1)` 이기 때문이다.

밟은 알파벳을 `Set`에 저장해주고, `Set`의 `contains()` 메소드를 이용해 검사를 할 생각이었다.

 

하지만 간과한게 하나 있었으니, 바로 `remove()` 메소드.

 

DFS는 밟지 못하게 될 때 까지 쭉 밟아보고, (방문여부를 `true`로 해주고) 경우가 충족되지 못했거나, 끝까지 돌았으면 일정 분기점으로 돌아와서 방문 여부를 `false`로 다시 변경해주는 과정을 밟는다.

하지만 `Set`을 사용하게 되면, 방문 여부를 `true`로 바꾸는게 `insert()`, 방문 여부를 다시 `false`로 바꿔주는게 `remove()`에 해당한다.▼

 

 

그런데 `remove()`의 시간복잡도는 `O(N)`으로 아무리 최대 26개라 해도, 움직이는 경우의 수가 너무 많아서 계산 횟수를 초과해버린다.

따라서 `Set`을 사용해서 문제를 해결하는 건 좋은 방법이 아니다.

 

실패한 풀이 2: alphabet 배열 사용

두번째 풀이 방법은 크기 26짜리의 alphabet 배열을 사용하는 것이다.

전부 숫자로 봐서 0번째는 A를 뜻하고, 1번째는 B를 뜻한다.

이런 식으로 A에 방문했다면 `alphabet[0] = true`로 해줘서 방문을 체크한다.

이렇게 방문 했다면 해당 인덱스의 부울 값을 `true`로, 방문 여부를 되돌리려면 해당 인덱스의 부울 값을 `false`로 바꿔주면 된다.▼

 

 

하지만 이것도 시간초과가 났다.

내 풀이가 이상한건가 싶어서 다른 언어의 풀이를 찾아봤는데, 비슷하게 풀었고 심지어 통과했다.

C++에서는 보통 200ms ~ 400ms 정도가 나왔는데, Swift에서는 시간초과다.

억울했지만, Swift에 맞은 사람들이 있길래 그 사람들은 어떻게 풀었는 지 찾아봤다.

 

맞은 풀이: 비트 마스킹

비트 마스킹까지 써야하나 싶은데, 안쓰면 통과가 안된다...

일단은 비트 마스킹에서도 알파벳을 숫자로 생각을 한다.

A는 0, B는 1 이런 식으로 말이다.

만약 C를 밟았다고 해보자.

C는 2에 해당하므로 이진수의 2번째 자리에 1을 밀어서(쉬프트 연산자 이용) 넣어준다.▼

 

 

이진수로는 4가 되겠지만, 우리는 이 이진수를 숫자로 볼 생각이 아니라 플래그로 볼 생각이다.

저렇게 C에 해당하는 순서의 이진수가 1이 되면 C를 밟았다는 의미이다.

 

이렇게 마킹을 해줬다면, AND연산자로 중복 체크를 해준다.

AND 연산은 둘 다 1일 때 1을 반환하고, 그 외의 경우엔 0을 반환한다.

즉, 둘이 같은 알파벳에 마킹이 되어있을 때 1을 반환하고, 마킹이 안되어있다면 0을 반환한다.▼

 

 

이렇게 체크를 해서 0이 반환되었다면, OR 연산으로 둘을 합쳐주고 다음 인자로 넘겨준다.

OR 연산은 둘 중 하나만 1이어도 1을 반환하고, 그 외의 경우엔 0을 반환한다.

하지만 둘 다 1인 경우는 앞에서 걸러주기 때문에 합쳐주는 연산으로 사용할 수 있다.▼

 

 

이렇게 합쳐준 비트를 계속 다음 인자로 넘겨주면서 어떤 알파벳이 체크됐는 지 검사할 수 있다.

하지만 비트를 넘겨준다고 했지만, 생각해보면 그냥 정수 하나 넘겨준거다.

정수 하나를 가지고 계산을 처리하기 때문에 앞의 방식들 보다 훨씬 빨라진다.

비트 마스킹 도대체 쓰는 사람이 있나 싶겠지만, 옛날 소스코드를 뜯어보면 꽤 있다.

참고로, 리눅스용 printf에서 플래그를 처리할 때 비트마스킹을 적극 사용한다.

 

 

Swift 코드

---

let RC = readLine()!.split(separator: " ").map { Int(String($0))! }
let R = RC[0], C = RC[1]
var map = Array(repeating: [Int](), count: R)
let dy = [-1, 1, 0, 0]
let dx = [0, 0, -1, 1]
var answer = 0

for i in 0..<R {
    map[i] = readLine()!.map { Int($0.asciiValue!) - 65 }
}

func DFS(_ y: Int, _ x: Int, _ count: Int, _ alphabet: Int) {
    answer = max(answer, count)
    for i in 0..<4 {
        let nextY = y + dy[i]
        let nextX = x + dx[i]

        if nextY < 0 || nextY >= R || nextX < 0 || nextX >= C {
            continue
        }
        let n = 1 << map[nextY][nextX]
        if alphabet & n == 0 {
            DFS(nextY, nextX, count + 1, alphabet | n)
        }
    }
}

DFS(0, 0, 1, 1 << map[0][0])
print(answer)