[C++] 백준 15686번 치킨 배달

구현 및 브루트 포스(완전 탐색) 문제.

처음에 잘못된 백트래킹과 dfs로 접근해서 시간초과를 많이 냈다.

백준 게시판에서 도움을 얻고, 겨우 풀었다.

 

처음 이 문제를 봤을 때

백트래킹으로 폐업시킬 치킨집을 정하고

그래프 탐색으로 (처음에는 BFS로 하려 했으나 코드로는 DFS로 했다.)

최단거리에 있는 치킨집의 거리를 다 구해서 더하고 어떤 치킨집들을 폐업시킬 때 최소 거리가 나오는지 구하려 했다.

 

이 방법은 시간초과가 났고, 게시판을 참고한 결과 다음과 같은 도움을 얻었다.

• 폐업시킬 치킨집을 고르는 것이 아닌, 그냥 치킨집들 중 어떤 치킨집들을 open할 지 결정하면 된다.
• 각 집들의 거리와 치킨집들의 거리를 저장해두고 쓰면, 굳이 도시들을 다시 살펴보지 않아도 된다.

이 두개가 이 문제의 keypoint인 것 같다.

 

문제풀이

백트래킹으로 푼 것은 변함이 없다. 다만 처음의 내 코드를 보자면,

/* */ #include <iostream> #include <cstring> #include <math.h> using namespace std; int widthHeight, numOfOpen, numOfClose; int city[51][51]; bool visit[51][51]; int chickenDistance; int cityDistance; int result = 1e10; void dfs(int startY, int startX, int currentY, int currentX) {     if (currentY < 1 || currentY > widthHeight || currentX < 1 || currentX > widthHeight) {         return;     }     if (visit[currentY][currentX]) { return; }     visit[currentY][currentX] = true;     if (city[currentY][currentX] == 2) {         int distance = abs(startY - currentY) + abs(startX - currentX);         chickenDistance = distance < chickenDistance ? distance : chickenDistance;         return;     }     dfs(startY, startX, currentY - 1, currentX - 1);     dfs(startY, startX, currentY - 1, currentX);     dfs(startY, startX, currentY - 1, currentX + 1);     dfs(startY, startX, currentY, currentX + 1);     dfs(startY, startX, currentY + 1, currentX + 1);     dfs(startY, startX, currentY + 1, currentX);     dfs(startY, startX, currentY + 1, currentX - 1);     dfs(startY, startX, currentY, currentX - 1); } void closeByBackTracking(int idx, int startY, int startX) {     if (idx > numOfClose) {         cityDistance = 0;         for (int i = 1; i <= widthHeight; i++) {             for (int j = 1; j <= widthHeight; j++) {                 if (city[i][j] == 1) {                     chickenDistance = 1e10;                     memset(visit, 0, sizeof(visit));                     dfs(i, j, i, j);                     cityDistance += chickenDistance;                 }             }         }         result = result < cityDistance ? result : cityDistance;         return;     }     else {         for (int i = startY; i <= widthHeight; i++) {             if (i > startY) { startX = 1; }             for (int j = 1; j <= widthHeight; j++) {                 if (city[i][j] == 2) {                     city[i][j] = 3;                     closeByBackTracking(idx + 1, i, j);                     city[i][j] = 2;                 }             }         }     } } int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     cout.tie(NULL);     cin >> widthHeight >> numOfOpen;     int numOfChickenHouse = 0;     for (int i = 1; i <= widthHeight; i++) {         for (int j = 1; j <= widthHeight; j++) {             cin >> city[i][j];             if (city[i][j] == 2) { numOfChickenHouse++; }         }     }     numOfClose = numOfChickenHouse - numOfOpen;     for (int i = 1; i <= widthHeight; i++) {         for (int j = 1; j <= widthHeight; j++) {             if (city[i][j] == 2) {                 city[i][j] = 3;                 closeByBackTracking(2, i, j);                 city[i][j] = 2;             }         }     }     cout << result;     return 0; }

위 처럼 이중포문을 계속 돌면서 2(치킨집)와 1(집)을 찾는 구조를 갖는다.

이는 백트래킹에서 50*50 = 2,500개의 집을 만일 2,500번 돈다면 6,250,000번을 계산해야 하고

후에 DFS를 돌면 최악의 경우 2,500번 연산하기 때문에 시간초과가 나게 된다.

따라서 이 문제는 이중 포문으로 푸는 것이 아니다.

 

이 문제는 집의 좌표와 치킨집의 좌표를 저장해둬야 한다.

그렇게 하면 굳이 도시의 모든 좌표를 다시 둘러볼 필요가 없기 때문이다.

그리고 나서 오픈할 치킨집들을 조합으로 결정한 후에, 해당 치킨집들의 좌표들과 집 좌표들을

계산한 값을 구해나가면서 어떤 조합이 최소의 도시 치킨거리를 갖는지 갱신해나가면 된다.

생각해내기 어려운 문제였다.

 

사용한 STL과 변수

절대값 메서드 abs()를 사용하기 위해 math.h를 사용했고, 최소값을 구하는 메서드 min()을 사용하기 위해 algorithm STL을 사용했다.

• widthHeight : 입력받는 n에 해당. 가로 세로의 길이
• numOfOpen : 입력받는 m에 해당. 최대로 열리는 치킨집의 개수
• chickenOpenPoint : 열린 치킨집들의 좌표를 저장하는 벡터
• homePoint : 집의 좌표들을 저장하는 벡터
• chickenPoint : 치킨집의 좌표들을 저장하는 벡터
• chickenDistance : 집 - 치킨집의 거리를 구하는 변수. 나중에 확인 가능하다.
• result : 결과값. 최초에 1e10으로 초기화해서 맨 처음 구한 거리는 무조건 갱신할 수 있도록 초기화 해뒀다.

백트래킹 메서드

백트래킹에서는 중요한 것이 있는데, 바로 가지치기를 잘 해주는 것이다.

이전에 했던 것들을 다시 탐색하지는 않는지, 이 점을 주목해서 구현해야 한다.

이것을 해결해 주는 것이 매개변수 lastCheck이다. 각 매개변수는 다음을 의미한다.

• idx : 현재 몇 번째 치킨집을 구하는 중인지. 만일 최대로 열릴 수 있는 개수보다 많이 탐색하려 한다면(이미 최대를 채웠다면) 조합이 완료된 것이므로 각 집에서 치킨집의 거리를 구한다.
• lastCheck : 마지막으로 구한 치킨집의 인덱스가 몇 번째인지 넘겨주는 매개변수이다. 이를 통해서 앞 -> 뒤로만 조합해주면 중복으로 조합하는 경우는 없으므로 경우의수가 상당히 줄어든다.

백트래킹 메서드의 로직은 idx가 문제의 M개 즉, 최대로 열리는 치킨집의 개수보다 높다면, 이미 조합을 완성한 것이므로 각 집에서 조합으로 결정한 치킨집들의 거리들 중 최소값들을 모두 더해서 현재 저장된 result값과 비교한다.

만약 M개보다 작다면 계속해서 조합을 한다.

 

메인함수

처음에 N과 M을 입력받는다.

그리고 input을 입력받는데, 1이면 집의 좌표를 저장하는 벡터에 저장하고 2라면 치킨집의 좌표를 저장하는 벡터에 저장한다.

 

그리고 반복문을 돌면서, 백트래킹으로 치킨집이 열리는 조합을 만들어준다.

완전탐색 문제라는 것을 본 후에야 풀 수 있었던 문제.

골드5와 실버1은 너무 다른 느낌이라서 접근할 때부터 쫄아있는 것 같다.

쫄지말고 접근해야 겠다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.