ใ ..ใ ใ ใ โฆ ์ ๋ฐ!!!!!!!! ์ง๋ฌธ ์ข ์ ์ฝ์!!!!!!!!!!!!!!
์์์ ๋ ์นธ (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)
๋๊ธ์ ์ฌ์ฉํ ์ ์์ต๋๋ค.