[c++] BOJ 2146 :: 다리 만들기

난이도 : 골드 3

걸린 시간 : 30분

 

문제

다리 만들기 문제 바로가기

2146번: 다리 만들기

 

풀이

• 가장 짧은 다리의 길이 == 가장 가까운 두 점 사이의 최단 거리
• 모든 섬 사이의 최단 거리를 구해야 함
• 각 섬에 속한 점들로부터 다른 섬의 점들까지의 최단 거리 계산
  • 가중치 없으므로 bfs 이용
  • 각 섬에 속하는 점들은 bfs로 따로 찾기

 

코드

#include <iostream>
#include <queue>

using namespace std;

int map[101][101];
int direction[4][2] = { {1,0}, {0,-1}, {-1, 0}, {0,1} };
vector<vector<pair<int, int>>> colorLand;

int bfs(int land, pair<int, int> start) {
    // land의 start 점에서 다른 land까지의 최소 거리 (x좌표 차이 + y좌표 차이)
    int dist = 1e9;
    for (int i = land + 1; i < colorLand.size(); i++) {
        // land idx 이상의 land에서만 진행하면 됨
        for (int j = 0; j < colorLand[i].size(); j++) {
            pair<int, int> pos = colorLand[i][j];
            int distTmp = abs(start.first - pos.first) + abs(start.second - pos.second)-1;
            if (distTmp < dist)
                dist = distTmp;
        }
    }
    return dist;
}

int main() {
    // 입력
    int N; cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }

    // 같은 섬에 속하는 육지 찾기
    queue<pair<int, int>> que;
    int colorIdx = -1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] != 1)
                continue;
            que.push(make_pair(i, j)); // 육지 색 칠하기
            map[i][j] = 0;

            vector<pair<int, int>> tmp; // 초기화
            colorLand.push_back(tmp);
            colorIdx++;

            while (!que.empty()) {
                pair<int, int> pos = que.front(); que.pop();
                colorLand[colorIdx].push_back(pos);
                int r = pos.first; int c = pos.second;
                for (int k = 0; k < 4; k++) {
                    int rp = r + direction[k][0];
                    int cp = c + direction[k][1];
                    if (rp < 0 || cp < 0 || rp >= N || cp >= N) // 맵 밖에 위치
                        continue;
                    if (map[rp][cp] != 1) // 육지가 아니면
                        continue;
                    que.push(make_pair(rp, cp));
                    map[rp][cp] = 0; // 0으로 없애버리기
                }
            }
        }
    }

    int minResult = 1e9;
    // 섬의 각 점마다 bfs 돌리기
    for (int i = 0; i < colorLand.size(); i++) { // 각 섬마다
        for (int j = 0; j < colorLand[i].size(); j++) { // 각 점마다
            int res = bfs(i, colorLand[i][j]);
            if (res < minResult)
                minResult = res;
        }
    }

    cout << minResult;
}

 

결과

문제	메모리	시간	언어	코드 길이
gmldms784	2472	48	C++17 / 수정	2376