[백준] 2146번*
💻 C++ 기반
✔️ 서로 다른 섬 사이의 거리를 구할 때 계속해서 dist 배열을 초기화하는 것은 비효율적
✔️ 각 지점이 cur 섬으로부터 얼마나 떨어져있는지와 next 섬으로부터 얼마나 떨어져있는지를 더하면 해결 가능
#include <cstdio>
#include <queue>
#include <utility>
#include <algorithm>
#define MAX 101
#define MAX_VALUE 987654321
using namespace std;
int m[MAX][MAX];
bool visited[MAX][MAX];
int dist[MAX][MAX];
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};
void categorize(int N, int startY, int startX, int num)
{
queue<pair<int, int> > q;
q.push(make_pair(startY, startX));
visited[startY][startX] = true;
while (!q.empty())
{
int curY = q.front().first;
int curX = q.front().second;
m[curY][curX] = num;
q.pop();
for (int i = 0; i < 4; i++)
{
int nextY = curY + dy[i];
int nextX = curX + dx[i];
if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N)
{
continue;
}
if (visited[nextY][nextX])
{
continue;
}
if (m[nextY][nextX] == 1)
{
q.push(make_pair(nextY, nextX));
visited[nextY][nextX] = true;
}
}
}
}
int getMinDist(int N)
{
queue<pair<int, int> > q;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (m[i][j] != 0)
{
q.push(make_pair(i, j));
dist[i][j] = 0;
}
}
}
int minimum = MAX_VALUE;
while (!q.empty())
{
int curY = q.front().first;
int curX = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int nextY = curY + dy[i];
int nextX = curX + dx[i];
if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N)
{
continue;
}
if (m[nextY][nextX] == m[curY][curX])
{
continue;
}
if (m[nextY][nextX] != 0)
{
minimum = min(minimum, dist[curY][curX] + dist[nextY][nextX]);
}
else
{
m[nextY][nextX] = m[curY][curX];
q.push(make_pair(nextY, nextX));
dist[nextY][nextX] = dist[curY][curX] + 1;
}
}
}
return minimum;
}
int main()
{
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
scanf("%d", &m[i][j]);
}
}
for (int i = 0; i < N; i++)
{
fill(visited[i], visited[i] + N, false);
}
int num = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (m[i][j] == 1 && !visited[i][j])
{
num++;
categorize(N, i, j, num);
}
}
}
for (int i = 0; i < N; i++)
{
fill(dist[i], dist[i] + N, -1);
}
int ans = getMinDist(N);
printf("%d", ans);
return 0;
}
Author And Source
이 문제에 관하여([백준] 2146번*), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jieun_han/백준-2146번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)