[BOJ 2146] 다리 만들기

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

2146번: 다리 만들기

문제 설명

0으로 이루어진 바다위에 떠있는 1로 이루어진 섬.

섬끼리 다리를 지으려고 하는데 가장 짧은 다리를 구하자.

 

인사이트

섬들 중 어느 섬이든 간에 가장 짧은 다리를 만드는 경우를 출력하면 된다.

1. 전체 BFS 순회를 통해 몇 개의 섬이 있으며 지도에 있는 1이 몇번째 섬에 부분에 해당하는지 파악
2. 지도를 이중 for loop를 통해 지도 값이 1 인 칸에 대하여 주위 네 개의 면 중 0이 있다면 큐에 넣는다.
   1. 큐에 들어온 좌표를 기준으로 BFS 를 실행
   2. 주위 네 개의 면 중 하나가 0 이면 큐에 push
   3. 주위 네 개의 면 중 하나가 1 이고 다른 섬이면 정답 벡터의 담기
      1. 시작 좌표, 끝 좌표를 이용해 |끝좌표 - 시작좌표| - 1 값을 구해 최소 다리 길이를 구함
3. 이중 for loop 가 끝나면 정답 벡터의 최솟값을 출력

 

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include<queue>

using namespace std;

int N, M;

int land[101][101];
int land_idx[101][101];
bool visited[101][101];
bool visited_idx[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<int> ans;
    cin >> N;
    //초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> land[i][j];
        }
    }

    //2차원 배열을 순회하면서 땅이 몇개인지 파악하고 각 행렬의 1이 속하는 땅의 번호를 기입
    int idx = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited_idx[i][j])continue;
            if (land[i][j] != 1)continue;
            queue<pair<int, int>> q;
            q.push(make_pair(i, j));
            visited_idx[i][j] = true;
            idx++;
            land_idx[i][j] = idx;

            while (!q.empty()) {
                int y = q.front().first;
                int x = q.front().second;

                q.pop();

                for (int k = 0; k < 4; k++) {
                    int ny = y + dy[k];
                    int nx = x + dx[k];
                    if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                    if (visited_idx[ny][nx])continue;
                    if (land[ny][nx] == 0)continue;
                    q.push(make_pair(ny, nx));
                    visited_idx[ny][nx] = true;
                    land_idx[ny][nx] = idx;
                }
            }
        }
    }


    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited[i][j])continue;
            if (land[i][j] != 1)continue;

            queue<pair<int, int>> q;
            //주변에 0이 있는 1인 시작점 찾아서 큐에 넣기
            bool check = false;
            for (int k = 0; k < 4; k++) {
                int ny = i + dy[k];
                int nx = j + dx[k];
                if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                if (land[ny][nx] == 0) {
                    if (land_idx[ny][nx] != land_idx[i][j])
                    {
                        check = true;
                    }
                }
                else {
                    continue;
                }
            }
            //4면 중 하나라도 0이면 큐에 담기
            if (check) {
                q.push(make_pair(i, j));
                visited[i][j] = true;
            } 
            //BFS
            while (!q.empty()) {
                int y = q.front().first;
                int x = q.front().second;

                q.pop();

                bool check = false;
                for (int k = 0; k < 4; k++) {
                    int ny = y + dy[k];
                    int nx = x + dx[k];
                    if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                    if (visited[ny][nx]) continue;
                    //4면 중 하나가 0 이면 큐에 푸시
                    if (land[ny][nx] == 0) {
                        if (land_idx[ny][nx] != land_idx[i][j])
                        {
                            q.push(make_pair(ny, nx));
                            visited[ny][nx] = true;
                        }
                    //4면 중 하나가 1이면 정답 벡터에 푸시
                    }else if (land[ny][nx] == 1) {
                        if (land_idx[ny][nx] != land_idx[i][j]) {
                            ans.push_back(abs(ny - i) - 1 + abs(nx - j));
                            break;
                        }
                    }

                }
            }
            //재탐색을 위한 방문 초기화
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(land[i][j] == 0)visited[i][j] = 0;
                }
            }

        }
    }

    cout << *min_element(ans.begin(), ans.end());
}