[C언어] 16234. 인구 이동

오늘 역테...너무 쉽게 나왔다.ㅜ,ㅠ

1번 큐브는 노가다라 2번 먼저 풀었는데, 2번 40분 컷인데 1번은 디버깅하다 시간 다 갔다ㅜ,ㅠ

정답 출력할 때, 인덱스 값을 잘 못 준거 같긴한데...확인할 길이 없으니ㅜ,ㅠ

둘 중 하나는 다들 푼 것 같아 면접이나 갈 수 있을지 모르것다!!!!!!!!!!

접근법

1. 단순 BFS이나 큐에 넣기 전 다음 칸의 값과 현재 칸의 값의 차가 일정 범위 안에 들어와야 큐에 넣는다.

2. 큐에 넣는 작업이 없을 때 까지 BFS를 반복해준다.

끝~

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int x, y, d;
}point;
 
int abs(int a, int b)
{
    return a - b < 0 ? -1 * (a - b) : a - b;
}
 
point Q[55 * 55];
int map[55][55], visit[55][55];
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
int Q_Front, Q_Back;
 
 
int main()
{
    int N, min, max, ans = 0;
    memset(map, -1, sizeof(map));
    scanf("%d %d %d", &N, &min, &max);
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            scanf("%d", &map[i][j]);
 
    int Flag = 0;
    while (1)
    {
        Q_Front = Q_Back = -1;
        memset(visit, 0, sizeof(visit));
        memset(Q, 0, sizeof(Q));
        Flag = 0;
 
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (visit[i][j] == 0)
                {
                    int count = 0;
                    int sum = 0;
                    int div = 0;
                    Q[++Q_Back].y = i;
                    Q[Q_Back].x = j;
                    Q[Q_Back].d = map[i][j];
                    visit[i][j] = 1;
 
                    count++;
                    sum = map[i][j];
 
                    while (Q_Front != Q_Back)
                    {
                        int y = Q[++Q_Front].y;
                        int x = Q[Q_Front].x;
                        int d = Q[Q_Front].d;
 
                        for (int k = 0; k < 4; k++)
                        {
                            int yy = y + dy[k];
                            int xx = x + dx[k];
 
                            if (map[yy][xx] == -1)
                                continue;
 
                            int temp = abs(d, map[yy][xx]);
 
                            if (visit[yy][xx] == 0 && temp >= min && temp <= max)
                            {
                                Q[++Q_Back].y = yy;
                                Q[Q_Back].x = xx;
                                Q[Q_Back].d = map[yy][xx];
                                visit[yy][xx] = 1;
                                count++;
                                sum += map[yy][xx];
                                Flag = 1;
                            }
                        }
                    }
                    div = sum / count;
                    for (int a = 1; a <= N; a++)
                    {
                        for (int b = 1; b <= N; b++)
                        {
                            if (visit[a][b] == 1)
                            {
                                map[a][b] = div;
                                visit[a][b] = -1;
                            }
                        }
                    }
 
                }
            }
        }
 
        if (Flag == 0)
            break;
 
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}