BOJ 2146 다리만들기

사용한 알고리즘

BFS, DFS

알고리즘 설명

일단 DFS로 각 육지로부터 닿아 있는 해상의 좌표를 Q에 넣는다.
이때에 각 육지를 방문한 순서로 idx를 매긴다.
모든 육지에서 위를 진행했다면, BFS를 진행한다.
BFS에서 해륙 상하좌우로 한칸씩 퍼져나가며 다른 idx를 가진 곳을 찾는다.
여기서 idx가 작은 순서로 퍼져나가기 시작한다.
BFS중, 자신과 다른 idx와 겹쳤다면, 두 대륙이 연결되는 다리가 만들어 진 것과 같다.
현재 idx 보다 작은 곳을 만난 경우, 그 지점은 그 시간에 이미 퍼져 나간 곳이다.
현재 idx 보다 큰 곳을 만난 경우, 그 지점은 그 시간에 퍼져나가지 못한 경우이다.
겹친 좌표가 현재 idx보다 작은 경우 t * 2 + 1, 현재 idx 보다 큰 경우 t * 2

풀이

// baekjoon 2146 yechan
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX_N = 101;
const int INF=1e9;
const int dir[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
typedef pair<pair<int, int>, int> P;
int N, cnt;
int board[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
queue<P> q;

void dfs(int x, int y, int idx) {
    if (x < 0 || x >= N || y < 0 || y >= N) return;
    if (visited[x][y]) return;
    if (!board[x][y]) return;
    visited[x][y]=true;
    q.push({{x, y}, idx});
    for (int d=0; d<4; d++)
        dfs(x+dir[d][0], y+dir[d][1], idx);
}

int bfs() {
    int depth=0;
    int ret=INF;
    while (!q.empty()) {
        int qSize = q.size();
        while (qSize--) {
            int cur_x = q.front().first.first;
            int cur_y = q.front().first.second;
            int cur_idx = q.front().second;
            q.pop();
            for (int d=0; d<4; d++) {
                int nx = cur_x + dir[d][0];
                int ny = cur_y + dir[d][1];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if (board[nx][ny] == 1) continue;
                if (board[nx][ny] == cur_idx) continue;
                if (board[nx][ny] == 0) {
                    board[nx][ny] = cur_idx;
                    q.push({{nx, ny}, cur_idx});
                }
                else {
                    ret = min(ret, depth*2 + (board[nx][ny] < cur_idx));
                }
            }
        }
        if (ret!=INF) return ret;
        depth++;
    }
    return -1;
}

int main(){
    scanf("%d", &N);
    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
            scanf("%d", &board[i][j]);

    cnt=2;
    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
            if (!visited[i][j] && board[i][j])
                dfs(i, j, cnt++);

    printf("%d\n", bfs());
    return 0;
}