[Algorithm] 백준 16234번 인구 이동

이제 삼성 소프트웨어 테스트도 조건 많이 걸어서 시간 줄이는 거 아니면 그냥 깡노가다로는 해결할 수 없음..

그래도 하다가 오기가 생겨서 노가다에 유사하게 진행하였음.

문제가 되었던 부분

1. 아래의 valueForVist 배열 크기를 잘못 잡은 것. 이것때문에 시간과 제출을 굉장히 많이함.
• 추후에는 배열은 vector로 예전처럼 진행할 것.
2. 오랜만에 C/C++ 코딩을 해서 그런지 단축키나 손에 익은 것이 없음.
• 이 부분도 매일 시간 또는 문제를 정해서 해결하도록 할 것.
3. grouping할 수 없는 케이스에 대해 true, false로 처리하려고 까불다가 꼬여버림.
• 코딩에서 가장 중요한 것 중 하나는 종료 조건 이기 때문에 해당 부분에 대해서 반복 학습 진행.

소스코드

#include <iostream>

int N, minV, maxV;

int map[60][60];

int visit[60][60];

int valueForVisit[2600];

using namespace std;

int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

int sumArea = 0, cntArea = 0;

void dfs(int px, int py, int v) {

int x, y;

if (px < 0 || py < 0 || px >= N || py >= N) return;

for (int i = 0; i < 4; i++) {

x = px + dx[i];

y = py + dy[i];

if (x >= 0 && y >= 0 && x < N && y < N) {

if (visit[x][y] == 0) {

if (abs(map[px][py] - map[x][y]) >= minV && abs(map[px][py] - map[x][y]) <= maxV) {

visit[x][y] = v;

sumArea += map[x][y];

cntArea++;

dfs(x, y, v);

}

}

}

}

}

int main()

{

cin >> N >> minV >> maxV;

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

cin >> map[i][j];

}

}

int answer = 0;

while (true) {

int lev = 1;

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

if (visit[i][j] == 0) {

visit[i][j] = lev;

sumArea = map[i][j];

cntArea = 1;

dfs(i, j, lev);

if (cntArea > 1) {

valueForVisit[lev] = sumArea / cntArea;

}

else {

visit[i][j] = 0;

valueForVisit[lev] = 0;

}

lev++;

}

}

}

if (lev - 1 == N * N) {

break;

}

for (int k = 1; k <= lev; k++) {

if (valueForVisit[k] == 0) continue;

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

if (visit[i][j] == k) {

map[i][j] = valueForVisit[k];

visit[i][j] = 0;

}

}

}

valueForVisit[k] = 0;

}

answer++;

}

cout << answer << endl;

return 0;

}