2146 다리만들기

다리 만들기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	192 MB	10320	3500	2205	31.994%

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은, 섬들을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

아이디어 구성까지는 좋았다.

영역별로 마스킹해서 하나하나 bfs로 다른 영역까지의 최소값을 구하는 식이었다.

그러나 계속 이상한 답이 나와서 구현하고나서도 30분넘게 디버깅만했다.

원인은... 다른영역찾았을때 bfs함수를 강종하고 다른 point에서 bfs를 수행하는데

전에 강종때문에 que가 초기화되지 않았던것...

que를 초기화해주니까 바로 해결되었다. 

다음엔 꼭 확인하자!

#include <bits/stdc++.h>

using namespace std;

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

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

struct Point {

int x;

int y;

};

int n;

int nation[101][101];

bool visited[101][101];

queue<Point> que;

queue<Point> edge;

void masking(int mask);

int bfs();

int main(){

freopen("input.txt","r",stdin);

ios::sync_with_stdio(false);

cin.tie(0);

cin>>n;

memset(nation, 0, sizeof(nation) );

memset(visited, false, sizeof(visited) );

int temp;

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

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

cin>>temp;

if(temp != 0){

nation[i][j] = temp;

}

}

}

int mask = 1;

for(int i=0; i<n; ++i){ //area masking

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

if( nation[i][j] && !visited[i][j] ){

visited[i][j] = true;

que.push({i,j});

masking(mask);

mask++;

//min_len = min_len < tmp ? min_len : tmp;

}

}

}

// for(int i=0; i<n; ++i){

// for(int j=0; j<n; ++j){

// cout<<nation[i][j]<<" ";

// }

// cout<<"\n";

// }

int min_len=200;

for(int i=0; i<n; ++i){ //find another area!

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

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

memset(visited,false, sizeof(visited));

que = queue<Point>();

que.push({i,j});

visited[i][j]=true;

//cout<<i<<", "<<j<<" to ";

temp = bfs() - 2;

min_len = min_len<temp ? min_len : temp; //save minimum length

}

}

}

cout<<min_len;

return 0;

}

int bfs(){

Point p;

int step_width;

int total_step=0;

int current_mask = nation[que.front().x][que.front().y];

//cout<<"what: "<<que.front().x<<", "<<que.front().y<<"\n";

while(!que.empty()){

step_width = que.size();

total_step ++;

for(int s=0; s<step_width; ++s){

p = que.front();

que.pop();

if( nation[p.x][p.y]!=current_mask && nation[p.x][p.y] != 0){

//cout<<" "<<p.x<<", "<<p.y<<" cost: "<<total_step<<"/ current: "<<current_mask<<" nation: "<<nation[p.x][p.y]<<"\n";

return total_step;

}

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

if(

(p.x+x_direction[i]>=0 && p.x+x_direction[i]<n) &&

(p.y+y_direction[i]>=0 && p.y+y_direction[i]<n) &&

(!visited[p.x+x_direction[i]][p.y+y_direction[i]]) &&

(nation[p.x+x_direction[i]][p.y+y_direction[i]] != current_mask) // is another place?

){

que.push({p.x+x_direction[i],p.y+y_direction[i]});

visited[p.x+x_direction[i]][p.y+y_direction[i]] = true;

}

}

}

}

//cout<<"nothing\n";

return 201;

}

void masking(int mask){

Point p;

while(!que.empty()){

p = que.front();

que.pop();

nation[p.x][p.y] = mask;

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

if(

(p.x+x_direction[i]>=0 && // >=0 important!

p.x+x_direction[i]<n) &&

(p.y+y_direction[i]>=0 &&

p.y+y_direction[i]<n) &&

(!visited[p.x+x_direction[i]][p.y+y_direction[i]]) &&

(nation[p.x+x_direction[i]][p.y+y_direction[i]] != 0)

){

visited[p.x+x_direction[i]][p.y+y_direction[i]] = true;

que.push({p.x+x_direction[i],p.y+y_direction[i]});

}

}

}

}