[BaekJoon/백준 15686번 치킨 배달

 

처음엔 복잡하게 구현했었다.

테스트케이스는 모두 맞길래, 제출했었는데 컴파일 에러가 발생했다.

 

아무리 봐도 알고리즘이 복잡하다는 생각을 하고는 있었기에,, 풀이 방법을 참고해봤고

 

내 알고리즘에서 생략할 수 있는 부분이 많이 있단 것을 깨닫고 수정했다.

 

 

이 문제는, 전체 치킨 지역 중에서 조합으로 치킨집을 M개 뽑은 뒤에

집 별로 거리계산을 하기만 해주면 되는 문제였다.

 

 

변경 전 처음 코드 (틀림)

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int MAP[50][50];
bool CHECK[50][50];
int DEPTH[50][50];

int N, M;

vector<pair<int, int>> HOME; // x, y
vector<int> CHICKEN; // x * N + y



vector<pair<int, int>> HOME_INFO[50]; // 치킨위치, 거리
vector<int> SELECT_CHICKEN; // 치킨집 뽑기

int TOTAL_DISTANCE = 50 * 50 * 50;

int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};

void bfs(int x, int y, int index) {
    
    queue<pair<int, int>> que;
    CHECK[x][y] = true;
    que.push({x, y});
    
    while(!que.empty()) {
        
        int xx = que.front().first;
        int yy = que.front().second;
        
        que.pop();
        
        
        for(int i = 0; i < 4; i++) {
            
            int tx = xx + mx[i];
            int ty = yy + my[i];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= N)
                continue;
            
            if(!CHECK[tx][ty]) {
                
                CHECK[tx][ty] = true;
                DEPTH[tx][ty] = DEPTH[xx][yy] + 1;
                
                que.push({tx, ty});
                
                if(MAP[tx][ty] == 2) {
                    
                    int coordi = tx * N + ty;
                    int distan = DEPTH[tx][ty];
                    HOME_INFO[index].push_back({coordi, distan});
                }
            }
            
        }
        
        
    }
    
}

void EVALUATE() {
    
    
    int H_S = HOME.size();
    int C_S = CHICKEN.size();
    int S_C_S = SELECT_CHICKEN.size();
    
    bool flag = false;
    
    int DISTANCE = 0;
    
    for(int i = 0; i < H_S; i++) {
        
        for(int j = 0; j < C_S; j++) {
            
            flag = false;
            
            for(int k = 0; k < S_C_S; k++) {
                
                if(HOME_INFO[i][j].first == SELECT_CHICKEN[k]) {
                    
                    flag = true;
                    DISTANCE += HOME_INFO[i][j].second;
                    
                    break;
                }
                
            }
            
            if(flag)
                break;
            
        }
        
    }
    
    if(TOTAL_DISTANCE > DISTANCE)
        TOTAL_DISTANCE = DISTANCE;
    
}

void dfs(int count) {
    
    
    if(count == M ) {
        
        EVALUATE();
        return;
    }
    
    
    int C_S = CHICKEN.size();
    
    for(int i = count; i < C_S; i++) {
        
        
        SELECT_CHICKEN.push_back(CHICKEN[i]);
        
        dfs(count + 1);
        
        SELECT_CHICKEN.pop_back();
        
    }
    
    
    
}

int main() {
    
    cin >> N >> M;
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            
            cin >> MAP[i][j];
            
            if(MAP[i][j] == 1)
                HOME.push_back({i, j});
            else if(MAP[i][j] == 2)
                CHICKEN.push_back((i * N) + j);
            
        }
    }
    
    int H_S = HOME.size();
    
    for(int i = 0; i < H_S; i++) {
        
        memset(CHECK, 0, sizeof(CHECK));
        memset(DEPTH, 0, sizeof(DEPTH));

        bfs(HOME[i].first, HOME[i].second, i);
        
    }
    
    
    
    dfs(0);
    
    cout << TOTAL_DISTANCE << "\n";
}

 

 

변경 후

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int MAP[50][50];

int N, M;

vector<pair<int, int>> HOME; // x, y
vector<pair<int, int>> CHICKEN; // x, y
vector<pair<int, int>> SELECT_CHICKEN; // x, y


int TOTAL_DISTANCE = 50 * 50 * 50;


void EVALUATE() {
    
    
    int H_S = HOME.size();
    int S_C_S = SELECT_CHICKEN.size();
    
    int DISTANCE = 0;
    
    for(int i = 0; i < H_S; i++) {
        
        int MIN = 50 * 50;
        
        for(int j = 0; j < S_C_S; j++) {
            
            int val = abs(HOME[i].first - SELECT_CHICKEN[j].first) + abs(HOME[i].second - SELECT_CHICKEN[j].second);
            
            if(MIN > val)
                MIN = val;
        }
        
        DISTANCE += MIN;
        
    }
    
    
    if(TOTAL_DISTANCE > DISTANCE)
        TOTAL_DISTANCE = DISTANCE;
}


void dfs(int index, int count) {
    
    
    if(count == M ) {
        
        EVALUATE();
        return;
    }
    
    
    int C_S = CHICKEN.size();
    
    for(int i = index; i < C_S; i++) {
        
        
        SELECT_CHICKEN.push_back(CHICKEN[i]);
        
        dfs(i + 1, count + 1);
        
        SELECT_CHICKEN.pop_back();
        
    }
    
    
    
}

int main() {
    
    cin >> N >> M;
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            
            cin >> MAP[i][j];
            
            if(MAP[i][j] == 1)
                HOME.push_back({i, j});
            else if(MAP[i][j] == 2)
                CHICKEN.push_back({i, j});
            
        }
    }
    
    
    dfs(0, 0);
    
    
    
    cout << TOTAL_DISTANCE << "\n";
}

 

너무 복잡하게, 어렵게 생각했었다.

 

 

소요 시간 : 1시간 30분