백준 완전탐색 알고리즘, 치킨배달 swift 문제풀이

 

 

 

 

안녕하세요. 개발자 멍구입니다. 

오늘은 백준의 15686번, 치킨배달문제 swift 문제풀이를 해보겠습니다. 곧바로 치킨배달 문제의 설명을 보겠습니다. 

 

 

 

---

백준 치킨배달 15686 
문제 설명

 

 

치킨배달은 골드5 티어의 문제로 일반적인 코딩테스트 기준, 중~중후반대로 나오는 문제라고 할 수 있습니다. 

 

 

 

 

 

해당 문제는 많은 사람이 풀이를 시도한 문제입니다. 시간제한은 1초입니다.

1초는 약 1억번의 연산까지 허용되는 것으로 알고 있습니다. 

 

크기가 N이 주어질때 도시의 크기는 NxN이 됩니다. 또한 거리를 구할때 |r1-r2| + |c1-c2|로 구하게 되는데 예를 들면 (0, 0)과 (2, 2)거리가 4가 됨을 의미합니다. 

 

 

 

 

 

N x N 크기의 도시가 있을때 0은 빈칸, 1은 집, 2는 치킨집인데 이때 2는 "치킨집이 될 수 있는 위치"입니다. 입력은 N, K가 주어지는데, K는 선택할 수 있는 최대 치킨집의 수입니다.

 

2인 위치 중에서 선택한 K개의 치킨집이 있을때, 치킨거리는 각각의 일반집과 가장 가까운 치킨집 간 거리의 합입니다. 

 

예를들어 N x N크기에서 K가 3이라면, 치킨집이 3인 모든 경우의 수 중 가장 치킨거리가 작은 경우를 구하면 됩니다. 더 이상의 예시를 적자면 설명이 길어지니 생략하겠습니다. 

 

 

 

 

 

예제 입력을 보겠습니다. 첫 예제 입력에서 5, 3은 각각 N과 K가 됩니다. 이는 "5x5 크기의 도시에서 3개의 치킨집을 선택한 경우의 수 중 가장 작은 치킨거리합을 구하는 문제가 됩니다."

 

 

 

---

치킨배달 문제 접근방법

해당문제는 다행히도 입력범위의 값이 작기 때문에 완전탐색으로 구할 수 있는 문제입니다. K개의 치킨집을 선택하는 모든 경우의 수를 탐색해서 가장 적은 치킨거리합을 구하면 되겠습니다. 

 

가령, NxN크기의 도시에서 2가 5개 있다면, 치킨집은 5곳에 존재할 가능성이 있습니다. 이때 만약 K가 3이라면 치킨집 위치후보인 5곳 중 3곳의 치킨집이 있을때의 경우의 수를 모두 돌리면 됩니다. 이 경우의 수는 순열, 재귀의 방법이 있는데 저는 재귀의 방법을 통해서 모든 경우의 수를 탐색해보겠습니다. 

 

이제 이어서 swift언어로 문제풀이를 진행해보겠습니다. 

 

 

 

---

치킨배달 문제 swift 문제풀이

 

 

 

1 ~ 2행) 먼저 N, K입력을 받습니다.

3행) 도시 그래프를 입력받을 이차원배열입니다. NxN크기의 그래프가 들어갑니다. 

4행) 재귀로 선택할 치킨집 좌표의 인덱스를 저장할 배열입니다. [1, 2, 3] / [1, 2, 4] / [1, 2, 5] / [1, 3, 4] / [1, 3, 5] / [1, 4, 5] / .... 등으로 배치될 치킨집 좌표의 의 인덱스를 저장하게 됩니다.

5행) 실제 출력할 정답변수입니다. 초기에는 임의로 Int.max값을 넣어두었습니다. 

 

 

 

 

그래프를 입력받는 부분입니다. 좀더 입력속도를 줄이기 위해서 입력받은 값을 Int로 변환하지 않고 Character타입으로 관리하겠습니다.

 

 

 

 

17 ~ 18행) hList는 일반집들의 좌표리스트, cList는 치킨집 좌표리스트입니다. 완전탐색 간 사용되어집니다. 

19 ~ 27행) 앞서 입력받은 2차원 Character 배열을 순회하면서 1일경우 일반집좌표로, 2일경우 치킨집좌표로 리스트에 저장을 합니다. 

 

 

 

 

 

치킨거리합을 구하는 로직입니다. order는 선택된 치킨집좌표의 인덱스를 가진다고 했죠, 현재 탐색중인 치킨집 경우에 대한 치킨거리(result)를 계산하고 있습니다. 

 

위의 이중 forEach 문을 간략하게 설명하자면, 특정 일반집에서(hList.forEach) 갈 수 있는 치킨집 좌표 인덱스(order.forEach)를 순회하면서 가장 적은 치킨거리를 구하는 것입니다.

 

 

 

 

 

실제 완전탐색을 돌리는 부분입니다. 재귀를 통해서 order리스트의 값을 변환시키면서 치킨집이 K개 선택될 수 있는 모든 경우의 수를 돌리며 getChickenDist() 메서드를 돌립니다. 

예로, 치킨집배치가능 위치가 3개, K가 2라면 배치되는 치킨집의 경우의 수(order) [0, 1] / [0, 2] / [1, 2]의 순으로 경우의 수가 발생합니다.

 

위의 코드가 이해하기 어려우시다면, 백준알고리즘 사이트의 N과M 문제를 연습해보시면 도움이 될 것 같습니다. 

 

 

 

 

 

DFS 재귀함수 호출 초기값을 0으로 시작하며(N과M문제 참고) 완전탐색을 돌리는 모습입니다. DFS 메서드 호출 간 NxN크기의 도시에서 K개의 치킨집을 선택했을 때의 모든 경우의 수를 돌면서 최소 치킨거리합을 구하게 됩니다. 

 

이후 완전탐색을 거치면 Ans에는 최소 치킨거리합 값이 들어가게 됩니다. 이렇게 구현한 코드의 결과는 아래와 같습니다.