16234

백준 16234번

Link: 16234번: 인구 이동

---

문제 설명

작년 하반기 삼성 SW 역량테스트 문제다.

시험장에서 문제 보고 뭔가싶어서 바로 넘기고 다른문제 올인하다 결국 둘다 못풀어서 광탈했던 악몽이 다시 떠오른다.

아무 문제나 붙잡고 풀다가 다 안풀려서 어차피 한번은 풀어야될 문제라 결국 붙잡고 풀었다.

예전부터 지인들이 니가 문제보고 쫄아서그렇지 별거 아닌문제다 라는 말을 했었는데 막상 풀어보니 틀린말은 아닌거같다.

하지만 내가 저날 시험장에서 이문제를 제대로 읽고 이해했다고 해도 시간안에 푸는건 무리였을것 같다.

BFS를 여러번 해야되는 문제다.

map에서 수정할 부분이 어디인지 찾아내는 부분에서 BFS를 해야 하고, 수정할 부분을 찾은 다음 map을 수정하기 위한 BFS를 해야하는 문제.

거기다 이 과정을 더이상 수정할 부분이 없을때까지 반복해야 한다.

BFS문제라는 느낌은 확실히 들었다.

처음에 문제 접했을땐 map에서 수정할 부분을 찾는 과정에 대해 BFS를 써야겠다는 생각이 안들었다.

그래서 3중 for문을 사용해서 수정할 부분을 찾아 마킹했다.

그 이후 map을 수정하는 부분에 대해서는 BFS로 구현하여 풀어보았다.

풀어본 다음 테스트케이스들을 넣어보니, 단순히 3중 for문으로는 풀수 없는 문제라는 것을 깨달았다.

마지막까지 가장 애먹였던 부분이 이부분인데, map에서 수정할 부분을 단순히 1로 마킹할 경우 영역간 경계가 있으나 이 경계를 무시하고 BFS를 진행하는 문제가 생긴다.

BFS로 바꿔서 해보고도 마지막에 이부분을 놓쳐 한번 더 삽질하다 결국 풀었다.

막상 풀고나니 별거 아닌건 맞는데, 시험장의 압박감과 이 시험볼 당시 알고리즘 공부도 어설프게 하고 간 나는 절대 못풀었을 것 같다는 생각이 들었다.

얻어가는 점은 몇번씩 실패하고도 남의 도움 안받고 내 힘만으로 풀어냈다는 점, BFS문제를 혼자 힘만으로 제대로 풀어냈다는 점이다.

이런 점을 밑거름삼아 앞으로 있을 역량테스트에서도 포기하지 않고 끝까지 풀어내는 것이 목표이다.

다시는 악몽 안꾸련다. 앞으로도 화이팅!!!

---

정답 코드

//
// Created by Keith_Lee on 15/01/2019.
//

#include <iostream>
#include <memory.h>
#include <queue>
#include <vector>

using namespace std;

int N, L, R;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int map[50][50] = {0, };
int toChange[50][50] = {0, };
int visit[50][50] = {0, };

vector<pair<int, int>> changes(){
    vector<pair<int, int>> result;

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(toChange[i][j] != 0){
                result.push_back(make_pair(i, j));
            }
        }
    }

    return result;
}

void toChange_init(){
    int areaCount = 1;

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            queue<pair<int, int>> Queue;
            Queue.push(make_pair(i, j));

            while(!Queue.empty()){
                int currentX = Queue.front().first;
                int currentY = Queue.front().second;
                Queue.pop();

                for(int k=0; k<4; k++){
                    int nextX = currentX + dx[k];
                    int nextY = currentY + dy[k];

                    if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < N){
                        int gap = abs(map[currentX][currentY] - map[nextX][nextY]);
                        if(gap >= L && gap <= R && toChange[nextX][nextY] == 0){
                            toChange[nextX][nextY] = areaCount;
                            Queue.push(make_pair(nextX, nextY));
                        }
                    }
                }
            }

            areaCount++;
        }
    }
}

void BFS(int currentX, int currentY){
    vector<pair<int, int>> visited;

    queue<pair<int, int>> Queue;
    Queue.push(make_pair(currentX, currentY));

    int changeCount = 0;
    int changeSum = 0;
    visit[currentX][currentY] = 1;

    while(!Queue.empty()){
        int startX = Queue.front().first;
        int startY = Queue.front().second;
        Queue.pop();

        changeCount++;
        changeSum += map[startX][startY];
        visited.push_back(make_pair(startX, startY));

        for(int i=0; i<4; i++){
            int nextX = startX + dx[i];
            int nextY = startY + dy[i];

            if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < N){
                if(visit[nextX][nextY] == 0 && toChange[nextX][nextY] == toChange[startX][startY]){
                    Queue.push(make_pair(nextX, nextY));
                    visit[nextX][nextY] = 1;
                }
            }
        }
    }

    for(int i=0; i<visited.size(); i++){
        map[visited[i].first][visited[i].second] = changeSum / changeCount;
    }
}

int main(){
    cin >> N >> L >> R;

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> map[i][j];
        }
    }

    int count = 0;

    while(true) {
        memset(toChange, 0, sizeof(toChange));
        memset(visit, 0, sizeof(visit));

        toChange_init();

        vector<pair<int, int>> ones = changes();
        if (ones.size() == 0) {
            break;
        }

        for (int i = 0; i < ones.size(); i++) {
            if (visit[ones[i].first][ones[i].second] == 0) {
                BFS(ones[i].first, ones[i].second);
            }
        }

        count++;
    }

    cout << count << '\n';

    return 0;
}

---