BOJ 2146: 다리 만들기 작성일 2020-02-29 https://www.acmicpc.net/problem/2146 2월동안 187문제 풀기(지난달 누적 87개) (71/187) 아주 유명한 다리 만들기 문제 생각보다 실수 할 요소가 매우 많다. 정신을 집중하는게 중요함 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include <bits/stdc++.h> using namespace std; int N; vector<vector<int>> arr, visit; struct Coord { int x,y; }; const int dx[4] = {0,0,-1,1}; const int dy[4] = {-1,1,0,0}; inline bool bound(int x) { return x >= 0 && x < N; } void sweep(int x, int y, queue<Coord>& q, vector<vector<int>>& visit) { visit[x][y] = 1; q.push({x,y}); for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if(!bound(nx) || !bound(ny) || arr[nx][ny] != 1) continue; arr[nx][ny] = 2; sweep(nx,ny,q,visit); } } int bfs(queue<Coord>& q, vector<vector<int>>& visit) { int depth = 0; while(int curSize = q.size()) { depth++; for(int sz = 0; sz < curSize; sz++) { Coord cur = q.front(); q.pop(); for(int i = 0; i < 4; i++) { int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; if(!bound(nx) || !bound(ny) || visit[nx][ny]) continue; if(arr[nx][ny] != 0) return depth-1; visit[nx][ny] = 1; q.push({nx,ny}); } } } return -1; } void print(vector<vector<int>>& arr) { for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) printf("%d ", arr[i][j]); printf("\n"); } } int main() { scanf("%d", &N); arr.resize(N, vector<int>(N)); for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) scanf("%1d", &arr[i][j]); int v = 2; int ans = 1e9; for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) if(arr[i][j] == 1) { vector<vector<int>> visit(N, vector<int>(N)); queue<Coord> q; sweep(i,j,q,visit); ans = min(ans, bfs(q,visit)); } printf("%d", ans); }