[DFS] 백준 1987번: 알파벳(Swift)

난이도: 골드 4

사용 언어: Swift

카테고리: DFS

https://www.acmicpc.net/problem/1987

code

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

var map = [[Int]]()
let direction: [(y: Int, x: Int)] = [
  (0,-1),
  (0,1),
  (-1,0),
  (1,0)
]
var result = 0

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

func dfs(start: (y: Int, x: Int), count: Int, bit: Int) {
  result = result > count ? result : count
  for i in 0..<direction.count {
    let nextP: (y: Int, x: Int) = (start.y + direction[i].y, start.x + direction[i].x)
    
    if (0..<r).contains(nextP.y)
        && (0..<c).contains(nextP.x) {
      let newB = 1 << map[nextP.y][nextP.x]
      if bit & newB == 0 {
        dfs(start: nextP, count: count + 1, bit: bit | newB)
      }
    }
  }
}

dfs(start: (0,0), count: 1, bit: 1 << map[0][0])
print(result)

🗒 지나간 알파벳을 단순히 배열에 담아서 확인했을 때 시간초과가 발생했다. 이유는 배열의 contains(_:)의 시간복잡도가 O(n)이다.
때문에 비트 연산자를 사용해 지나간 알파벳을 확인해야 시간초과 없이 통과되었다.
예를들어, 알파벳 A, B, C, D가 있을 때
알파벳을 아스키코드 - 65를 하여,
A -> 0
B -> 1
C -> 2
D -> 3 으로 만들어준다.
위 값을 1에 << 비트 연산자를 이용하여 각
A -> 0001
B -> 0010
C -> 0100
D -> 1000 으로 만든다. 여기서 bit가 0011이면, 지나간 알파벳이 A와 B가 된다.