[BEAKJOON] 2146_다리 만들기_C언어

https://www.acmicpc.net/problem/2146

풀이

1. 배열을 입력 받을 때 큐에 지도상에 1인 부분들을 저장한다.

2. 다리를 놓을라고 탐색을 할 때 같은 섬에 연결하는 것을 방지하기 위하여 섬 마다 번호를 다르게 바꾸어준다.

3. 배열을 입력 받을 때 사용한 큐로 BFS를 해준다. 이때 테두리만 탐색해주면 되기 때문에 섬의 테두리 마다 BFS를 해주어 가장 작은 값을 출력해준다.

풀이는...간단하다. 구현이 나한테는 길로 복잡해서 그렇지..

제출한 코드

#include <stdio.h>
void input();
void Q_reset();
void check_reset();
void map_reset();
int partion(int y, int x, int Num);
int map[110][110], check[110][110], n;
int map_x[10000], map_y[10000], map_front = -1, map_back = -1;
int Q_x[10000], Q_y[10000], Q_front, Q_back, min=999999;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };
 
 
int main()
{
    map_reset();
    input();
 
    while (map_front <= map_back)
    {
        int x = map_x[++map_front];
        int y = map_y[map_front];
        if (map[y + 1][x] == 0 || map[y - 1][x] == 0 || map[y][x + 1] == 0 || map[y][x - 1] == 0)//섬의 테두리 부분이면 BFS
        {
            //printf("%d %d\n",y,x);
            int num = map[y][x];
            check_reset();
            Q_reset();
            Q_x[++Q_back] = x;
            Q_y[Q_back] = y;
            //printf("/ %d %d\n", y, x);
            check[y][x] = 1;
            while (Q_front <= Q_back)
            {
                int xx = Q_x[++Q_front];
                int yy = Q_y[Q_front];
                //printf("// %d %d\n", yy,xx);
                for (int i = 0; i < 4; i++)
                {
                    int xxx = xx + dx[i];
                    int yyy = yy + dy[i];
                    if (xxx < 1 || yyy<1 || yyy>n || xxx>n)
                        continue;
 
                    if (map[yyy][xxx] == 0 && check[yyy][xxx]==0)
                    {
                        //printf("///%d %d\n", yyy,xxx);
                        check[yyy][xxx] = check[yy][xx] + 1;
                        Q_x[++Q_back] = xxx;
                        Q_y[Q_back] = yyy;
                    }
                    if (map[yyy][xxx]!=num&&map[yyy][xxx] != 0 && map[yyy][xxx] != -2)
                    {
                        if (check[yy][xx] -1 < min)
                        {
                            min = check[yy][xx] - 1;
                        }
                    }
                }
            }
        }
    }
 
    printf("%d\n",min);
    return 0;
}
 
int partion(int y, int x, int Num)//섬의 번호를 다르게 만들어준다.
{
    map[y][x] = Num;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx<1 || yy<1 || yy>n || xx>n || map[yy][xx] != -1)
            continue;
 
        partion(yy, xx, Num);
    }
    return 1;
}
 
 
void input()//입력 받는다.
{
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &map[i][j]);
            if (map[i][j])
            {
                map[i][j] = -1;
                map_x[++map_back] = j;
                map_y[map_back] = i;
            }
        }
    }
    int num = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (map[i][j] == -1)
            {
                num += partion(i, j, num);
            }
        }
    }
}
 
void Q_reset()
{
    Q_front = Q_back = -1;
    for (int i = 0; i<10000; i++)
        Q_x[i] = Q_y[i] = 0;
}
 
void check_reset()
{
    for (int i = 0; i < 110; i++)
    {
        for (int j = 0; j < 110; j++)
        {
            check[i][j] = 0;
        }
    }
}
 
void map_reset()
{
    for (int i = 0; i < 110; i++)
        for (int j = 0; j < 110; j++)
            map[i][j] = -2;
}