[백준/BOJ] 1987번 알파벳 (Swift 스위프트)

문제 난이도: 골드 4

 

사용 알고리즘: DFS, 백트래킹

 

Set을 통해 한번 방문한 알파벳을 저장해놨다.

Set은 중복값이 없기 때문에 이럴 때 유용한 것 같다.

 

아무튼 코드 자체는 기존 dfs와 다를게 없지만, visited.remove를 통해서 방문했던 곳은 다시 삭제해주는 코드로 짜주었다.

방문한 알파벳을 지워주지 않으면, direction의 순서에 따라서 먼저 들어간 곳에 따라서 최대치가 바뀌기 때문에 모든 경로를 파악하여 맥스값을 프린트해주는 방법밖에 없었다.

import Foundation

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

var map: [[String]] = []
var visited: Set<String> = []
let directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]

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

func dfs(x: Int, y: Int) -> Int {
    
    visited.insert(map[y][x])
    
    var maxCount = visited.count

    for direction in directions {
        let newX = x + direction.0
        let newY = y + direction.1

        if newX >= 0, newX < c, newY >= 0, newY < r, !visited.contains(map[newY][newX]) {
            maxCount = max(maxCount, dfs(x: newX, y: newY))
        }
    }

    visited.remove(map[y][x])
    return maxCount
}

print(dfs(x: 0, y: 0))

 

결과는 '시간초과'

이 방법 외에는 잘 모르겠어서 다른 사람들의 풀이를 보니 비트마스킹을 통해 문제를 푼 것을 확인했다.