백준 2146 다리만들기

#include <cstdio>

#include <iostream>

#include <queue>

using namespace std;

int N, island_num=1, border_cnt, ans=100000;

int arr[110][110];

bool visit[110][110];

int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { 1, 0, -1, 0 };

queue<int> queuex, queuey;

void init();

void dfs(int x, int y, int num);

void border_bfs(int x, int y, int num);

int main()

{

scanf(" %d", &N);

for (int i = 0; i < N; i++){

for (int j = 0; j < N; j++){

scanf(" %d", &arr[i][j]);

}

}

for (int i = 0; i < N; i++){

for (int j = 0; j < N; j++){

//육지이고 번호가 정해지지 않은 섬일 경우에만(1일 경우) 실행

if (arr[i][j] == 1){

++island_num;//섬 번호 증가

dfs(i, j, island_num);

}

}

}

for (int i = 0; i < N; i++){

for (int j = 0; j < N; j++){

if (arr[i][j] != 0){

init();

border_bfs(i, j, arr[i][j]);

}

}

}

printf("%d\n", ans);

return 0;

}

void dfs(int x, int y, int num){

//지도 밖으로 나가지 않고

if (x >= 0 && y >= 0 && x < N&& y < N){

//그룹화 되지 않은 육지이면

if (arr[x][y] == 1){

arr[x][y] = num;

for (int dir = 0; dir < 4; dir++){

dfs(x + dx[dir], y + dy[dir], num);

}

}

else{

return;

//printf("예외1\n");

}

}

else{ //지도 밖으로 나가는 경우는 아무것도 안함.

return;

}

}

void init(){

for (int i = 0; i < N; i++){

for (int j = 0; j < N; j++){

visit[i][j] = false;

}

}

}

void border_bfs(int x, int y, int num){

queuex.push(x); queuey.push(y);

visit[x][y] = true;

while (!queuex.empty() && !queuey.empty()){

int tempx = queuex.front(), tempy = queuey.front();

queuex.pop(); queuey.pop();

//queue에 저장

//방문하지 않은 정점만 방문

for (int dir = 0; dir < 4; dir++){

int nextX = tempx + dx[dir], nextY = tempy + dy[dir];

if (visit[nextX][nextY] == false){

//지도 밖으로 나가는 경우

if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N){

continue;

}

//자신의 영역일 경우

else if (arr[nextX][nextY] == num){

continue;

}

//갈 수 있는 바다일 경우

else if (arr[nextX][nextY] == 0){

visit[nextX][nextY] = true;

queuex.push(nextX);

queuey.push(nextY);

}

else{//다른 섬의 테두리에 도착하였을 경우

int absX, absY;

if (x >= nextX)

absX = x - nextX;

else

absX = nextX - x;

if (y >= nextY)

absY = y - nextY;

else

absY = nextY - y;

//값 계산

ans = ans < absX + absY - 1 ? ans : absX + absY - 1;

//큐에 남아있는것들 제거

while (!queuex.empty() && !queuey.empty()){

queuex.pop(); queuey.pop();

}

return;

}

}

else{ continue; }

}

}

}