๊ธ€ ์ž‘์„ฑ์ž: ์ด์ง€์›๐ŸŒฉ๏ธ

ใ…‹..ใ…‹ใ…‹ใ…‹โ€ฆ ์ œ๋ฐœ!!!!!!!! ์ง€๋ฌธ ์ข€ ์ž˜ ์ฝ์ž!!!!!!!!!!!!!!

์ž„์˜์˜ ๋‘ ์นธ (r1, c1)๊ณผ (r2, c2) ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ๋Š” |r1-r2| + |c1-c2|๋กœ ๊ตฌํ•œ๋‹ค.


(r1, c1), (r2, c2)๋ฅผ (r1, r2), (c1, c2)๋กœ ์ฝ์–ด์„œ ์‚ฝ์งˆ ์˜ค์ง€๊ฒŒ ํ–ˆ๋‹ค.

๋ฌธ์ œ

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


๋‚ด๊ฐ€ ์ž‘์„ฑํ•œ ์ฝ”๋“œ

Swift

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = input[0]
let m = input[1]
var board = [[Int]]()
var chicken = [(Int, Int)]()
var house = [(Int, Int)]()
for _ in 0..<n {
let line = readLine()!.split(separator: " ").map { Int(String($0))! }
board.append(line)
}
for i in 0..<n {
for j in 0..<n {
if board[i][j] == 1 {
house.append((i + 1, j + 1))
} else if board[i][j] == 2 {
chicken.append((i + 1, j + 1))
}
}
}
// ์กฐํ•ฉ ๊ตฌํ•˜๊ธฐ
var results = [[(Int, Int)]]()
var picked = [(Int, Int)]()
var visited = Array(repeating: false, count: chicken.count)
func pick(toPick: Int, start: Int) {
if toPick == 0 {
results.append(picked)
return
}
for i in start..<chicken.count {
if visited[i] {
continue
}
visited[i] = true
picked.append(chicken[i])
pick(toPick: toPick - 1, start: i + 1)
picked.removeLast()
visited[i] = false
}
}
pick(toPick: m, start: 0)
var ans = 987654321
for result in results {
var sum = 0
for h in house {
var distance = 987654321
for c in result { // ํ•œ ์ง‘์˜ ์น˜ํ‚จ ๊ฑฐ๋ฆฌ ๊ตฌํ•˜๊ธฐ
let dist = abs(c.0 - h.0) + abs(c.1 - h.1)
distance = min(distance, dist)
}
sum += distance
}
ans = min(sum, ans)
}
print(ans)
๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€

๋Œ“๊ธ€์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.