공부/알고리즘
BOJ 15686. 치킨 배달
도리암
2022. 11. 13. 15:46
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
처음 이 문제를 봤을 때는 그리디 알고리즘을 떠올렸다.
가장 멀리 있는 치킨집들부터 없애면 손쉽게 정답을 구할 수 있을 것 같았다.
하지만 실제로 구현해보니 틀린 부분이 발생했다.
왜일까? 반례는 다음과 같았다.
5 1
2 1 0 1 2
0 0 0 0 0
0 0 2 0 0
0 0 0 0 0
2 1 0 1 2
ans: 12
5 4
2 1 0 1 2
0 0 0 0 0
0 0 2 0 0
0 0 0 0 0
2 1 0 1 2
ans: 4이처럼 같은 형태의 배치도에서 삭제할 치킨집들의 개수가 달라질 때
1개를 남겨야 하는 경우 가운데 치킨집을 남겨야 정답이 나오며
4개를 남겨야 하는 경우 반대로 가운데 치킨집을 남기면 정답이 나오지 않게 된다.
그래서 새로 고안한 방법은 그냥 백트래킹을 이용해서 m개의 치킨집이 남았을 때 각 치킨집에 대한 치킨거리를 구하는 것이었다.
변수 이름을 길게 썼더니 보기가 좀 힘들긴 하지만,
간단히 설명해보면 숙소(1)와 치킨집(2)의 위치 정보를 각각의 배열에 담았고
숙소에서 모든 치킨집에 대한 치킨 거리를 구해 저장했다.
이후 vis 배열을 통해 몇번째 치킨 집을 남겨놓을 것인지를 백트래킹으로 만들었고
미리 구해놓은 치킨거리 배열에서 vis가 1인 부분의 치킨거리를 구했다.
