백준 15686 치킨 배달 - JAVA

15686 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

 

 

알고리즘 설명

---

브루트포스 문제를 풀면 풀수록 구구단부터 시작된 한국의 교육방식에 절여져 있는 뇌를 빼고 생각해야하는 것 같습니다. 머리속에서는 시각적으로 보여지는 좌표지도를 통해서 폐업하면 안되는 치킨집을 찾아버리기 때문에, 자꾸 그 생각에 지배되는 것 같습니다. 해당 문제를 쉽게 정리하면, 치킨집의 개수에서 조합을 사용하여 M개의 치킨집과 집과의 거리의 최단거리를 누적합하고, 누적합된 거리를 비교하여 가장 값이 작은 거리를 선정하는 알고리즘입니다. 폐업하지 않을 치킨집 M개 선정은 depth를 0으로 두고, depth가 M과 같아진다면 집과 치킨집과의 거리를 계산합니다. 계산하여 저장된 누적합은 백트래킹을 활용해 모든 누적합들을 비교하고, 최소값을 도출하면 어렵지 않게 풀 수 있을것이라고 생각합니다.

visit배열에서 true처리된 원소를 depth가 M과 같아지면, 다시 visit배열을 false처리하는 것이 백트래킹의 핵심입니다.

 

처음 문제를 접했을 때, BFS문제와 비슷한 그래프가 주어져서 큐를 활용해 풀다가 꽤나 애를 먹었습니다. 한번에 문제가 요구하는 방식을 찾아 해결하면 베스트겠지만, 저처럼 험난한 과정을 겪으신 분들도 계실거라 생각합니다. 하지만 이 또한 코딩 실력이 늘어가는 과정 중에 하나라고 생각합니다.

 

코드 해석

---

 

N×N 크기의 지도 배열 arr를 입력받습니다. 입력받은 배열의 원소가 1이라면 house 리스트에, 2라면 chiken 리스트에 저장합니다. chikenDist 함수에서 start부터 시작해서 M개의 치킨집을 하나씩 선택하고, 각 조합에 대해 집에서 가장 가까운 치킨집을 맨해튼 거리를 활용하여 계산합니다. 탐색과 계산이 끝나면 백트래킹을 위해 visit배열을 false값으로 되돌리고, sum의 값을 선택된 치킨집의 조합들을 기준으로 최소값을 도출합니다.

 

- 참고 -

• 맨해튼 거리는 2차원 좌표에서 두 점 a와 b 사이의 거리를 구하는 방법으로, 두 점 사이의 각 x좌표값의 차이의 절대값과 y좌표값의 차이의 절대값의 합으로 구할 수 있습니다.
  예를 들어 a좌표 값이 (a1,a2)이고 b좌표 값이 (b1, b2)라면 맨해튼 거리는 |a1 - b1| + |a2 - b2| 입니다.