99클럽 코테 스터디 23일차 TIL: 완전탐색 + 백트래킹

문제

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

풀이

치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력하는 문제

치킨집을 고르는 것은 조합을 구하는 것을 의미한다.
조합을 구하는 코드는 다음과 같이 짰다.

func dfs(i: Int, selected: [(Int, Int)]) {
    if selected.count == m {
        result = min(result, getDistance(coord: selected))
        return
    }

    for index in i..<chicken.count {
        dfs(i: index + 1, selected: selected + [chicken[index]])
    }
}

동일한 치킨집을 뽑으면 안되기 때문에 뽑은 치킨집 다음 치킨집 부터 탐색할 수 있도록 index 값을 파라미터로 받았다.
치킨집을 뽑았으면, 특정집에서 가장 가까운 치킨집을 고르는 작업을 진행해야한다.

한 집에서 모든 치킨집을 확인해봐야 한다.

해당 코드는 다음과 같이 구현했다.

func getDistance(coord: [(Int, Int)]) -> Int {
    var distance = 0
    for h in house {
        var minDistance = Int.max
        for c in coord {
            minDistance = min(minDistance, abs(h.0 - c.0) + abs(h.1 - c.1))
        }
        distance += minDistance
    }
    return distance
}

여기서 받는 coord 파라미터가 치킨집을 뽑은 조합을 의미한다.
전체 코드는 다음과 같다.

소스코드

	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let n = input[0], m = input[1]
	var house: [(Int, Int)] = []
	var chicken: [(Int, Int)] = []
	for y in 0..<n {
	let graph = readLine()!.split { $0 == " " }.map { Int($0) }
	for x in 0..<n {
	if graph[x] == 1 {
	house.append((y, x))
	}
	if graph[x] == 2 {
	chicken.append((y, x))
	}
	}
	}
	var result = Int.max
	dfs(i: 0, selected: [])
	print(result)
	func dfs(i: Int, selected: [(Int, Int)]) {
	if selected.count == m {
	result = min(result, getDistance(coord: selected))
	return
	}
	for index in i..<chicken.count {
	dfs(i: index + 1, selected: selected + [chicken[index]])
	}
	}
	func getDistance(coord: [(Int, Int)]) -> Int {
	var distance = 0
	for h in house {
	var minDistance = Int.max
	for c in coord {
	minDistance = min(minDistance, abs(h.0 - c.0) + abs(h.1 - c.1))
	}
	distance += minDistance
	}
	return distance
	}

view raw 15686_치킨 배달.swift hosted with ❤ by GitHub

후기

치킨집을 뽑는 부분에서 백트래킹 기법이 들어간다.
그리고 한 집에서 모든 치킨집에 대한 거리를 구해서 최소 거리를 구해야 하는 문제

크게 어렵지 않은 문제였다.