[백준] 2146번 : 다리 만들기

문제

 

---

풀이

 

일단 다른 섬끼리 다리를 이어야 하기 때문에 각각의 섬을 구분해야 한다.

이런식으로 말이다.

 

myunji.tistory.com/280

[백준] 2667번 : 단지번호붙이기

이 문제에서처럼 dfs를 사용해 각 섬을 구분지을 것이다.

 

그리고 가장자리에 위치한 모든 땅들에 대해 bfs로 최단거리를 구하는데

만약 이전의 bfs로 구해놓은 최단거리가 4 였다면

거리가 4보다 커질 때 bfs 탐색을 종료해 시간을 아낀다.

---

소스코드

 

#include <iostream>
#include <queue>
#include <vector>
#include <utility>

using namespace std;

vector<vector<int>> map; //지도
vector<pair<int, int>> side_land; //가장자리에 있는 땅들
int min_block = 1000, N;
pair<int, int> dir[4] = {{-1, 0},  //상
                         {1,  0},  //하
                         {0,  -1}, //좌
                         {0,  1}}; //우

void dfs(pair<int, int> cur, int mark) { //각 섬마다 다르게 마크
    bool isSide = false; //가장자리의 땅인가?
    int row = cur.first;
    int col = cur.second;

    map[row][col] = mark; //구역 체크
    for (int i = 0; i < 4; i++) {
        int nr = row + dir[i].first;
        int nc = col + dir[i].second;
        if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < N)) { //범위 체크
            if ((map[nr][nc] == 0) && !isSide) { //물이 있으면 가장자리 땅. 중복 투입 막기 위해 isSide 사용
                isSide = true;
                side_land.push_back(make_pair(row, col));
            } else if (map[nr][nc] == 1) //연결된 땅이 있으면 dfs
                dfs(make_pair(nr, nc), mark);
        }
    }
}

void bfs(pair<int, int> start, int mark) {
    vector<vector<int>> dist; //거리 저장
    queue<pair<int, int>> q;
    dist.assign(N, vector<int>(N, 0));

    q.push(start);
    dist[start.first][start.second] = 0; //시작점은 0
    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();

        if ((map[row][col] < 0) && (map[row][col] != mark)) { //마크가 다른 땅이면 새로운 땅에 닿은 것
            min_block = dist[row][col];
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;
            if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < N) && (map[nr][nc] != mark) && (dist[nr][nc] == 0)) { //새로운 섬이거나, 물이거나
                dist[nr][nc] = dist[row][col] + 1;
                if (dist[nr][nc] > min_block) //현재의 가장 짧은 다리보다 길면 더이상 탐색할 필요가 없음
                    return;
                q.push(make_pair(nr, nc));
            }
        }
    }
}

int main() {
    int mark = 0; //각 섬마다 -1, -2,...로 마크

    cin >> N;
    map.assign(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cin >> map[i][j];
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 1) { //체크가 안된 땅에 대해 dfs로 섬 찾기
                mark--;
                dfs(make_pair(i, j), mark);
            }
        }
    }
    for (int i = 0; i < side_land.size(); i++) //가장자리 땅들에 대해 bfs
        bfs(side_land[i], map[side_land[i].first][side_land[i].second]);
    cout << min_block - 1;
}

전체 소스코드다.

 

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 1) { //체크가 안된 땅에 대해 dfs로 섬 찾기
                mark--;
                dfs(make_pair(i, j), mark);
            }
        }
    }

각 섬은 음수(mark)로 표기할 것이다.

 

void dfs(pair<int, int> cur, int mark) { //각 섬마다 다르게 마크
    bool isSide = false; //가장자리의 땅인가?
    int row = cur.first;
    int col = cur.second;

    map[row][col] = mark; //구역 체크
    for (int i = 0; i < 4; i++) {
        int nr = row + dir[i].first;
        int nc = col + dir[i].second;
        if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < N)) { //범위 체크
            if ((map[nr][nc] == 0) && !isSide) { //물이 있으면 가장자리 땅. 중복 투입 막기 위해 isSide 사용
                isSide = true;
                side_land.push_back(make_pair(row, col));
            } else if (map[nr][nc] == 1) //연결된 땅이 있으면 dfs
                dfs(make_pair(nr, nc), mark);
        }
    }
}

이어진 땅들을 모두 같은 mark로 표기하는 dfs함수다.

 

        if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < N)) { //범위 체크
            if ((map[nr][nc] == 0) && !isSide) { //물이 있으면 가장자리 땅. 중복 투입 막기 위해 isSide 사용
                isSide = true;
                side_land.push_back(make_pair(row, col));
            } else if (map[nr][nc] == 1) //연결된 땅이 있으면 dfs
                dfs(make_pair(nr, nc), mark);
        }

가장자리의 땅을 효율적으로 탐색하기 위해 땅의 상하좌우에 물이 있다면 side_land 벡터에 넣어준다.

중복 입력을 막기 위해 isSide 변수를 둬서 이미 가장자리라고 체크한 땅인지 확인한다.

 

    for (int i = 0; i < side_land.size(); i++) //가장자리 땅들에 대해 bfs
        bfs(side_land[i], map[side_land[i].first][side_land[i].second]);

dfs를 하면서 모은 side_land에 대해 bfs를 실행한다.

 

void bfs(pair<int, int> start, int mark) {
    vector<vector<int>> dist; //거리 저장
    queue<pair<int, int>> q;
    dist.assign(N, vector<int>(N, 0));

    q.push(start);
    dist[start.first][start.second] = 0; //시작점은 0
    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();

        if ((map[row][col] < 0) && (map[row][col] != mark)) { //마크가 다른 땅이면 새로운 땅에 닿은 것
            min_block = dist[row][col];
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;
            if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < N) && (map[nr][nc] != mark) && (dist[nr][nc] == 0)) { //새로운 섬이거나, 물이거나
                dist[nr][nc] = dist[row][col] + 1;
                if (dist[nr][nc] > min_block) //현재의 가장 짧은 다리보다 길면 더이상 탐색할 필요가 없음
                    return;
                q.push(make_pair(nr, nc));
            }
        }
    }
}

bfs 함수다.

 

        if ((map[row][col] < 0) && (map[row][col] != mark)) { //마크가 다른 땅이면 새로운 땅에 닿은 것
            min_block = dist[row][col];
            return;
        }

만약에 이번 좌표가 0이 아니라면 땅이라는 것이다. 만약 그 땅이 처음 시작 좌표의 mark와 다른 값이라면

새로운 땅에 닿은 것이다. 그럼 min_block을 갱신한다.

 

min_block = min(min_block, dist[row][col])처럼 비교를 하지 않는 이유를 궁금해 할 수도 있다.

bfs를 진행하면서 현재의 min_block 보다 값이 커지면 바로 리턴을 하기 때문에 조건에 맞는 dist[row][col]은 항상 기존의 min_block보다 작은 값이다.

 

        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;
            if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < N) && (map[nr][nc] != mark) && (dist[nr][nc] == 0)) { //새로운 섬이거나, 물이거나
                dist[nr][nc] = dist[row][col] + 1;
                if (dist[nr][nc] > min_block) //현재의 가장 짧은 다리보다 길면 더이상 탐색할 필요가 없음
                    return;
                q.push(make_pair(nr, nc));
            }
        }

최단거리를 구하는 평범한 bfs에 더이상 탐색할 필요가 없는지 확인하는 코드를 추가했다.