[백준] 2146번 다리 만들기 (= bridge building) - 재우스 프로그래밍 (C 언어)

문제 링크 : www.acmicpc.net/problem/2146

#include <stdio.h>
#include <stdbool.h>

#define DEBUG 0
#define MAX_MAP_SIZE 100

typedef struct _Node {
    int islandNum;    //0은 바다, 1은 번호 안 준 육지, 2부터 번호 부여한 육지
    bool side;    //true이면 side(다리를 놓을 수 있음), false이면 다리를 놓을 수 없음
} Node;

typedef struct _QueueNode {
    int xPos;
    int yPos;
    int length;
} QueueNode;

typedef struct _Queue {
    QueueNode arrQueue[MAX_MAP_SIZE * MAX_MAP_SIZE];
    int front;
    int back;
} Queue;
Queue queue;

int count;    //arrSideLand에 실제 저장된 데이터 개수
int mapSize;    //입력될 좌표의 한 변 길이
Node graph[MAX_MAP_SIZE][MAX_MAP_SIZE];    //graph 크기는 mapSize * mapSize
bool visited[MAX_MAP_SIZE][MAX_MAP_SIZE];    //방문을 체크하는 배이므로 graph와 동일한 크기
QueueNode arrSideLand[MAX_MAP_SIZE * MAX_MAP_SIZE];    //최대 섬의 개수는 전체 좌표 개수보다 작다.
//x좌표, y좌표, 섬의 번호를 한 노드에 저장한다.

void giveIslandNumBFS(int, int, int);    //섬에 숫자를 부여해주는 함수
void sideLand(void);    //arrSideLand에 0이 붙어있는 모든 육지 좌표 저장
int minRouteBFS(int, int, int, int);
void checkSide(void);    //graph의 모든 좌표에 대해 옆에 바다(= 0)이 붙어 있는지 없는지에 대해 저장
void push(int, int, int);
bool empty(void);
void initNode(Node *);
void initGraph(void);
void initVisited(void);
void initQueue(void);
#if DEBUG
void printGraph(void);    //graph 출력하는 함수
#endif

int main(void)
{
    scanf("%d", &mapSize);

    initQueue();    //queue 초기화
    initGraph();    //graph 초기화
    //graph 값 입력 받아서 저장
    for (int i = 0; i < mapSize; i++) {
        for (int j = 0; j < mapSize; j++) {
            scanf("%d", &graph[i][j].islandNum);
        }
    }

    int islandNum = 2;    //각 섬에 부여할 숫자
    //1로 저장한 육지를 섬 단위로 숫자 2부터 부여
    for (int i = 0; i < mapSize; i++) {
        for (int j = 0;j < mapSize; j++) {
            if (graph[i][j].islandNum == 1) {
                giveIslandNumBFS(i, j, islandNum);    //(i, j) 위치에 연결된 육지에 islandNum 값으로 섬에 숫자 부여
                islandNum++;    //다음 섬의 숫자
            }
        }
    }
    //graph 출력
#if DEBUG
    printGraph();
#endif

    int min = mapSize + mapSize - 2;    //다리 길이의 최솟값 저장
    int temp = min;


    checkSide();    //섬의 가장자리가 될 수 있는 조건 중 하나가 옆에 0인 바다가 최소 한개 이상 붙어있어야 하므로 옆에 바다가 붙어있는지 여부를 true false로 저장
    sideLand();        //섬의 가장자리 육지만 필요하므로 뽑아서 따로 배열 생성

    for (int i = 0; i < count; i++) {
        for (int j = 0; j < count; j++) {
            //현재 좌표의 섬 번호와 다른 섬 번호라면
            if (arrSideLand[j].length != arrSideLand[i].length) {
                initQueue();    //queue 초기화
                initVisited();    //방문 여부 초기화
                visited[arrSideLand[j].xPos][arrSideLand[j].yPos] = false;    //목표 섬은 방문되어 있다는 표시를 지워줘야 도달 가능
                temp = minRouteBFS(arrSideLand[i].xPos, arrSideLand[i].yPos, arrSideLand[j].xPos, arrSideLand[j].yPos);    //i 섬 좌표로부터 j 섬 좌표까지의 거리 계산
                //한 개의 섬에 둘러싸야 있는 경로는 목표에 도달하지 못하는 경우가 생김(옆이 바다가 있다고 해서 무조건 다른 섬에 도달 가능한 경우가 아니기 때문)
                if (temp == -1) {
                    continue;
                }
                //섬 사이의 거리가 최소 2이므로 더 이상 탐색할 필요가 없을 때는 빠르게 프로그램 종료를 시켜준다.
                else if (temp == 2) {
                    printf("1\n");
                    return 0;
                }

                min = min > temp ? temp : min;    //최솟값 갱신
            }
        }
    }

    printf("%d\n", min - 1);

    return 0;
}

//모든 섬에 2, 3, 4, ... 순서로 번호 부여하는 함수
void giveIslandNumBFS(int xPos, int yPos, int islandNum)
{
    initQueue();    //queue 초기화
    push(xPos, yPos, 0);    //숫자 부여할 섬의 첫 육지를 queue에 push
    graph[xPos][yPos].islandNum = islandNum;    //queue에 push한 좌표는 islandNum 숫자 부여
    queue.front++;    //queue의 front 증가

    while (!empty()) {
        int frontXPos = queue.arrQueue[queue.front].xPos;
        int frontYPos = queue.arrQueue[queue.front].yPos;

        //아래쪽 좌표가 islandNum 1인 초기 육지일 때
        if (frontXPos - 1 >= 0 && graph[frontXPos - 1][frontYPos].islandNum == 1) {
            push(frontXPos - 1, frontYPos, 0);    //아래쪽 좌표를 queue에 삽입
            graph[frontXPos - 1][frontYPos].islandNum = islandNum;    //queue에 삽입하는 좌표의 섬 번호 부여(앞으로 탐색이 안됨)
        }
        //위쪽 좌표가 islandNum 1인 초기 육지일 때
        if (frontXPos + 1 < mapSize && graph[frontXPos + 1][frontYPos].islandNum == 1) {
            push(frontXPos + 1, frontYPos, 0);    //상동
            graph[frontXPos + 1][frontYPos].islandNum = islandNum;
        }
        //왼쪽 좌표가 islandNum 1인 초기 육지일 때
        if (frontYPos - 1 >= 0 && graph[frontXPos][frontYPos - 1].islandNum == 1) {
            push(frontXPos, frontYPos - 1, 0);    //상동
            graph[frontXPos][frontYPos - 1].islandNum = islandNum;
        }
        //오른쪽 좌표가 islandNum 1인 초기 육지일 때
        if (frontYPos + 1 < mapSize && graph[frontXPos][frontYPos + 1].islandNum == 1) {
            push(frontXPos, frontYPos + 1, 0);    //상동
            graph[frontXPos][frontYPos + 1].islandNum = islandNum;
        }
        queue.front++;    //queue에서 탐색할 다음 데이터 가리킴
    }

    return;
}

//바다와 연결된 모든 섬 좌표와 섬 번호를 arrSideLand 에 저장
void sideLand(void)
{
    for (int i = 0; i < mapSize * mapSize; i++) {
        arrSideLand[i].xPos = -1;
        arrSideLand[i].yPos = -1;
        arrSideLand[i].length = 0;
    }
    for (int i = 0; i < mapSize; i++) {
        for (int j = 0; j < mapSize; j++) {
            //섬 번호가 2 이상으로 부여 받고 && 옆에 바다가 있는 좌표라면 배열에 저장
            if (graph[i][j].islandNum > 1 && graph[i][j].side) {
                arrSideLand[count].xPos = i;
                arrSideLand[count].yPos = j;
                arrSideLand[count].length = graph[i][j].islandNum;
                count++;
            }
        }
    }

    return;
}

//섬 번호가 다른 두 좌표 사이의 최단 거리를 계산해서 return 하는 함수
//경로가 없으면 return -1
int minRouteBFS(int startX, int startY, int endX, int endY)
{
    push(startX, startY, 0);    //출발 좌표 queue에 삽입
    queue.front++;    //-1에 있던 front 0으로 증가

    //도착 좌표에 도달한다면 두 좌표 사이의 거리를 return 하지만
    //도착 좌표에 결국 도달하지 못하고 queue가 비어버린다면 경로가 섬 내부에 갇히는 것이므로 -1 return
    //1 1 1 0
    //1 0 1 0
    //1 1 1 0
    //0 0 0 1    에서 (0, 1) 좌표는 바다를 끼고 있지만 (3, 3)에 도달 불가능
    while (!empty()) {
        int frontXPos = queue.arrQueue[queue.front].xPos;
        int frontYPos = queue.arrQueue[queue.front].yPos;
        int frontLength = queue.arrQueue[queue.front].length;

        //현재 좌표가 위쪽 벽에 붙어있지 않고 && 위쪽 좌표가 경로계산을 위한 방문을 아직 하지 않았을 때
        if (frontXPos - 1 >= 0 && !visited[frontXPos - 1][frontYPos]) {
            push(frontXPos - 1, frontYPos, frontLength + 1);    //위쪽 좌표 값과 거리 1 증가시켜서  queue에 삽입 
            visited[frontXPos - 1][frontYPos] = true;    //queue에 넣은 좌표는 방문했다고 check
            //만약 위쪽 좌표가 최종 좌표라면 저장된 거리 반환
            if (visited[endX][endY]) {
                return queue.arrQueue[queue.back].length;
            }
        }
        //아래쪽 좌표로 상동
        if (frontXPos + 1 < mapSize && !visited[frontXPos + 1][frontYPos]) {
            push(frontXPos + 1, frontYPos, frontLength + 1);
            visited[frontXPos + 1][frontYPos] = true;
            if (visited[endX][endY]) {
                return queue.arrQueue[queue.back].length;
            }
        }
        //왼쪽 좌표로 상동
        if (frontYPos - 1 >= 0 && !visited[frontXPos][frontYPos - 1]) {
            push(frontXPos, frontYPos - 1, frontLength + 1);
            visited[frontXPos][frontYPos - 1] = true;
            if (visited[endX][endY]) {
                return queue.arrQueue[queue.back].length;
            }
        }
        //오른쪽 좌표로 상동
        if (frontYPos + 1 < mapSize && !visited[frontXPos][frontYPos + 1]) {
            push(frontXPos, frontYPos + 1, frontLength + 1);
            visited[frontXPos][frontYPos + 1] = true;
            if (visited[endX][endY]) {
                return queue.arrQueue[queue.back].length;
            }
        }

        queue.front++;
    }
    return -1;
}

//바다와 붙어 있는 육지에는 side 변수에 true 저장
void checkSide(void)
{
    for (int i = 0; i < mapSize; i++) {
        for (int j = 0; j < mapSize; j++) {
            if (graph[i][j].islandNum > 0) {
                //위쪽 좌표가 바다(= 0)라면 true 저장
                //네 방면중 한 곳이 있든 전부 있든 상관 없으므로 하나라도 통과되면 더 이상 검사 안함
                if (i - 1 >= 0 && graph[i - 1][j].islandNum == 0) {
                    graph[i][j].side = true;
                }
                else if (i + 1 < mapSize && graph[i + 1][j].islandNum == 0) {
                    graph[i][j].side = true;
                }
                else if (j - 1 >= 0 && graph[i][j - 1].islandNum == 0) {
                    graph[i][j].side = true;
                }
                else if (j + 1 < mapSize && graph[i][j + 1].islandNum == 0) {
                    graph[i][j].side = true;
                }
            }
        }
    }
    return;
}

void push(int xPos, int yPos, int length)
{
    queue.back++;    //queue의 back 증가
    queue.arrQueue[queue.back].xPos = xPos;
    queue.arrQueue[queue.back].yPos = yPos;
    queue.arrQueue[queue.back].length = length;

    return;
}
bool empty()
{
    if (queue.front > queue.back) {
        return true;
    }
    else {
        return false;
    }
}

void initNode(Node *inputNode)
{
    inputNode->islandNum = 0;
    inputNode->side = false;
    return;
}
void initGraph()
{
    for (int i = 0; i < MAX_MAP_SIZE; i++) {
        for (int j = 0; j < MAX_MAP_SIZE; j++) {
            initNode(&graph[i][j]);
        }
    }
    return;
}
void initVisited(void)
{
    for (int i = 0; i < MAX_MAP_SIZE; i++) {
        for (int j = 0; j < MAX_MAP_SIZE; j++) {
            if (graph[i][j].islandNum > 0) {
                visited[i][j] = true;
            }
            else {
                visited[i][j] = false;
            }
        }
    }
    return;
}
void initQueue()
{
    for (int i = 0; i < MAX_MAP_SIZE * MAX_MAP_SIZE; i++) {
        queue.arrQueue[i].xPos = -1;
        queue.arrQueue[i].yPos = -1;
        queue.arrQueue[i].length = -1;
    }
    queue.front = -1;
    queue.back = -1;

    return;
}
#if DEBUG
void printGraph(void)
{
    printf("graph\n");
    for (int i = 0; i < mapSize; i++) {
        for (int j = 0; j < mapSize; j++) {
            printf("%d ", graph[i][j].islandNum);
        }
        printf("\n");
    }
    printf("\n");
    return;
}
#endif