다리 만들기 (feat. 백준, 2146번)

다리 만들기
https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int arr[100][100], dx[4], dy[4], N, ans;
bool visit[100][100];
void func1(){
    register int number = 1;
    queue<pair<int, int>> q;
    for(register int i = 0, j, x, y, d, nx, ny; i < N; ++i)
        for(j = 0; j < N; ++j)
            if(arr[i][j] == -1){
                q.push(make_pair(i, j));
                arr[i][j] = number;
                while(!q.empty()){
                    x = q.front().first, y = q.front().second; q.pop();
                    for(d = 0; d < 4; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(0 <= nx && nx < N && 0 <= ny && ny < N && arr[nx][ny] == -1)
                            arr[nx][ny] = number, q.push(make_pair(nx, ny));
                    }
                }
                ++number;
            }
}
void func2(){
    queue<tuple<int, int, int>> q;
    for(register int i = 0, j, number, x, y, cnt, d, nx, ny; i < N; ++i)
        for(j = 0; j < N; ++j)
            if(arr[i][j]){
                number = arr[i][j];
                memset(visit, false, sizeof(visit));
                q.push(make_tuple(i, j, 0));
                visit[i][j] = true;
                while(!q.empty()){
                    x = get<0>(q.front()), y = get<1>(q.front()), cnt = get<2>(q.front()); q.pop();
                    if(cnt >= ans)  // ans보다 크거나 같으면 bfs를 진행할 이유가 없음
                        continue;
                    for(d = 0; d < 4; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(0 <= nx && nx < N && 0 <= ny && ny < N && !visit[nx][ny]){
                            visit[nx][ny] = true;
                            if(arr[nx][ny] == 0)
                                q.push(make_tuple(nx, ny, cnt + 1));
                            else if(arr[nx][ny] != number && ans > cnt)
                                ans = cnt;
                        }
                    }
                }
            }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    ans = 999999999;
    cin >> N;
    for(register int i = 0, j; i < N; ++i)
        for(j = 0; j < N; ++j){
            cin >> arr[i][j];
            if(arr[i][j] == 1)
                arr[i][j] = -1;
        }
    func1();        // 섬마다 고유번호를 붙이기 위한 bfs. 첫번째 섬의 (i, j)는 모두 1을, 두번째 섬의 (i, j)는 모두 2를 삽입
    func2();        // 섬과 섬 사이가 바다인 경우, 섬과 섬의 고유번호가 다른 경우, 최소값을 찾기 위한 bfs.
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

1. 다음 문제는 2개의 bfs를 수행하여 풀이하였습니다.
2. 첫번째 bfs는 섬에 번호를 붙이기 위한 bfs입니다. (func1 함수)
3. 두번째 bfs는 섬에서 다른 섬까지의 최소값을 찾는 bfs입니다. (func2 함수)