백준 - 2146 [C++]

 이 문제는 bfs 를 이용해서 푸는 문제이다. 이 문제에서 핵심은 섬이 꼭 육지로만 이루어져 있지 않을 수 있다는 것이다. 겉면이 육지로 둘러싸이고 내부는 바다일 수 있는 것이다. 따라서 외곽을 찾아서 bfs 를 돌릴 때 내가 출발한 섬의 번호와 같은 육지에 도착하면 실패하도록 구현해야 한다.

 두번째로 bfs2 에서 while 문 내부에서 리턴하지 못하고 모두 끝나고 리턴할 때의 리턴값을 잘 설정해야 한다. 나는 처음에 아무 생각 없이 -1로 놨었는데, 그렇게 하면 최소를 구하는 문제에서 -1이 정답으로 나오는 케이스가 발생할 수 있다. 그러므로 최소를 구하는 문제에서는 리턴값을 가장 크게, 최대를 구하는 문제에서는 리턴값을 가장 작게 설정해줘야 한다.

 

 

 

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int matrix[100][100];
int n;

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

vector<vector<int>> dist;

bool inRange(int y, int x)
{
	if (0 <= y && y < n && 0 <= x && x < n)
	{
		return true;
	}
	return false;
}

void bfs(int startY, int startX, int island)
{
	queue<pair<int, int>> q;

	matrix[startY][startX] = island;
	q.push({ startY, startX });

	while (!q.empty())
	{
		pair<int, int> present = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextY = present.first + dy[i];
			int nextX = present.second + dx[i];

			if (inRange(nextY, nextX) && matrix[nextY][nextX] == 1)
			{
				matrix[nextY][nextX] = island;
				q.push({ nextY, nextX });
			}
		}
	}
}

int bfs2(int startY, int startX, int island)
{
	queue<pair<int, int>> q;

	dist = vector<vector<int>>(n, vector<int>(n, 0));
	dist[startY][startX] = 1;
	q.push({ startY, startX });

	while (!q.empty())
	{
		pair<int, int> present = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextY = present.first + dy[i];
			int nextX = present.second + dx[i];

			if (inRange(nextY, nextX) && matrix[nextY][nextX] != 0 &&
				matrix[nextY][nextX] != island)
			{
				return dist[present.first][present.second] - 1;
			}

			if (inRange(nextY, nextX) && dist[nextY][nextX] == 0 &&
				matrix[nextY][nextX] == 0)
			{
				dist[nextY][nextX] = dist[present.first][present.second] + 1;
				q.push({ nextY, nextX });
			}
		}
	}

	return 10001;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int island, answer;

	cin >> n;

	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < n; x++)
		{
			cin >> matrix[y][x];
		}
	}

	island = 2;

	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < n; x++)
		{
			if (matrix[y][x] == 1)
			{
				bfs(y, x, island++);
			}
		}
	}

	answer = 10001;
	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < n; x++)
		{
			if (matrix[y][x] >= 2)
			{
				bool isEdge = false;

				for (int i = 0; i < 4; i++)
				{
					int tempY = y + dy[i];
					int tempX = x + dx[i];

					if (inRange(tempY, tempX) && matrix[tempY][tempX] == 0)
					{
						isEdge = true;
					}
				}

				if (isEdge)
				{
					answer = min(answer, bfs2(y, x, matrix[y][x]));
				}
			}
		}
	}
	
	cout << answer << '\n';

	return 0;
}