백준 - 쿠키크루 - 22939 - swift

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

22939번: 쿠키크루

 

완전탐색 및 구현 문제라고 볼 수 있다. 

 

처음에 가장 가까운 토핑들만 탐색하는 bfs로 접근했는데 틀렸다. 

사실 그 방법으로도 의문점이 있었다. 반례가 존재할 것 같았다. 

집 - [토핑 1, 2, 3] - 도착지점 

이렇게 bfs로 탐색한다고 해서 최소거리가 보장 된다는 점이 없다는 것이다. 

 

그래서 이 점을 해결하기 위해 순열로 각 토핑들의 방문위치를 정해주는 것이다. 

총 3개의 토핑들이 있으므로, 총 6개의 방문방법이 존재하다.

 

이렇게 하면 사실 bfs도 필요없어진다. 

이 문제는 방문할 수 없는 위치도 존재하지 않기 때문에, 

그냥 두 점사이의 거리로 계산해도 최소거리가 된다. 

 

let N = Int(readLine()!)!

var arr: [[String]] = []
var home = (0,0)
var end = (0,0)
var cookies: [String: [(Int,Int)]] = [:]
for i in 0..<N {
    let list = readLine()!.map{String($0)}
    arr.append(list)
    for j in 0..<N {
        if list[j] == "H" {
            home = (i,j)
        } else if list[j] == "#" {
            end = (i,j)
        } else if list[j] != "X" {
            cookies[list[j], default: []].append((i,j))
        }
    }
}

let dir = [(0,1),(0,-1),(1,0),(-1,0)]

func find(_ x: String) -> (Int) {
    var minDist = 999999
    func permutation(_ idx: Int, _ list: [Int] ) {
        if list.count == 3 {
            var sum = 0
            sum += dist(start: home, end: cookies[x]![list[0]] )
            sum += dist(start: cookies[x]![list[0]], end: cookies[x]![list[1]] )
            sum += dist(start: cookies[x]![list[1]], end: cookies[x]![list[2]] )
            sum += dist(start: cookies[x]![list[2]], end: end)
            minDist = min(minDist, sum)
        } else {
            for i in 0..<3 {
                if !list.contains(i) {
                    permutation(i+1, list+[i])
                }
            }
        }
    }
    permutation(0, [])
    
    return (minDist)
}

func dist(start:(Int,Int), end: (Int,Int)  ) -> Int {
    return abs(start.0-end.0) + abs(start.1-end.1)
}

var ans = [(String, Int)]()
ans.append(("Assassin",find("J")))
ans.append(("Healer",find("C")))
ans.append(("Mage",find("B")))
ans.append(("Tanker",find("W")))

let sorted = ans.sorted(by: {$0.1 < $1.1})
let filtered = sorted.filter{sorted.first!.1 == $0.1 }.sorted{$0.0 < $1.0}

print(filtered.first!.0)