#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
queue<pair<int, int>> q;
queue<pair<int, int>> q_label[100];
void bfs(int a, int b);
void bfs_2(int lab_c);
int n;
int dp[100][100] = {0};
int label[100][100] = {0}, label_count = 1;
int arr[100][100];
bool label_visit[100];
bool visited[100][100];
int bridge = 1000000;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void init()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// if (label[i][j] == 0)
visited[i][j] = false;
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
cin >> arr[i][j];
if (arr[i][j])
{
q.push(make_pair(i, j));
dp[i][j] = 1;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (!visited[i][j] && arr[i][j])
{
bfs(i, j);
label_count++;
}
}
}
// for (int i = 0; i < n; i++)
// {
// for (int j = 0; j < n; j++)
// {
// cout << label[i][j] << " ";
// }
// cout << "\n";
// }
for (int i = 1; i <= label_count; i++)
{
init();
bfs_2(i);
}
cout << bridge;
}
void bfs(int a, int b)
{
queue<pair<int, int>> temp;
temp.push(make_pair(a, b));
visited[a][b] = true;
while (!temp.empty())
{
int x = temp.front().first;
int y = temp.front().second;
temp.pop();
label[x][y] = label_count;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (arr[nx][ny] == 1 && label[nx][ny] == 0 && !visited[nx][ny] && nx < n && nx >= 0 && ny < n && ny >= 0)
{
visited[nx][ny] = true;
label[nx][ny] = label_count;
temp.push(make_pair(nx, ny));
}
}
}
}
void bfs_2(int lab_c)
{
queue<pair<int, int>> q_temp;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (label[i][j] == lab_c)
{
visited[i][j] = true;
dp[i][j] = 0;
q_temp.push(make_pair(i, j));
}
}
}
while (!q_temp.empty())
{
int x = q_temp.front().first;
int y = q_temp.front().second;
q_temp.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (!visited[nx][ny] && nx < n && nx >= 0 && ny < n && ny >= 0)
{
visited[nx][ny] = true;
dp[nx][ny] = dp[x][y] + 1;
if (label[nx][ny] != 0 && label[nx][ny] != lab_c)
{
bridge = min(bridge, dp[x][y]);
return;
}
q_temp.push(make_pair(nx, ny));
}
}
}
}
풀 코드이다
나 이거 풀면서 머리가 빠질뻔했다
라벨링 까진 생각해냈는데, 뇌용량을 너무 많이 써서인지 거리구하는게 잘 안구해지더라고 ㅋㅋ
다른사람들 풀이를 보면, 섬의 가장자리의 값들을 기준으로 거리를 구햇지만 나같은 경우엔
q값에다가 각 라벨링한 섬의 위치들을 넣고 dp식을 진행해주었다.
