[BOJ] 2589 보물섬

Link https://www.acmicpc.net/problem/2589

Note

어딘가에 숨어있는 보물의 최단거리의 최대 경우를 탐색하는 문제
DFS는 시도해보지 않았지만 경우의 수가 커질 경우 DFS는 시간초과가 예상이 된다.

모든 육지에 대해서 BFS를 진행해야한다.
20 by 20에서 모든 위치를 L로 초기화 시켜서 돌려보았더니 1초를 살짝 넘은후 결과가 나와서 Timeout을 예상했지만
시간이 1초인 만큼 최대 결과도 맞춰 놓은것 같다.
BFS를 무작정 많이 시도 하면 된다.
땅의 위치를 배열에 저장한 후 풀면 n * m 만큼 반복문을 안돌리고 땅의 갯수만큼만 돌리면 된다.

알고리즘

1. 보물지도 정보를 받아온다. 동시에 땅의 위치를 배열에 저장한다.
2. 땅의 갯수만큼 각 지점에 대해서 BFS를 진행한다. 각 지점에 대해서 최대 경우의 수를 비교해 갱신한다.
3. 계산된 최대 경우의 수를 출력한다.

소스코드

#include <iostream>
#include <queue>

using namespace std;

struct Point {
	short x;
	short y;

	Point() {} 
	Point(short x, short y) : x(x), y(y) {}
};

const int MAX = 50;
char tresureMap[MAX][MAX + 1];
Point lands[MAX * MAX];
int row, col;

const short posX[4] = { 1, 0, -1, 0 };
const short posY[4] = { 0, 1, 0, -1 };

int main()
{
	short landCount = 0;
	int maxDis = 0;

	cin >> row >> col;

	for (int i = 0; i < row; i++)
	{
		cin >> tresureMap[i];
		for (int j = 0; j < col; j++)
			if (tresureMap[i][j] == 'L')
				lands[landCount++] = Point(i, j);
	}

	for (int i = 0; i < landCount; i++)
	{
		bool point[MAX][MAX] = {};
		int dis = 0;

		queue<Point> curQ;
		queue<Point> nextQ;

		curQ.push(lands[i]);

		while (!curQ.empty())
		{
			while (!curQ.empty())
			{
				Point cur = curQ.front();
				curQ.pop();

				if (point[cur.x][cur.y])
					continue;

				point[cur.x][cur.y] = true;

				for (int pos = 0; pos < 4; pos++)
				{
					short nextX = cur.x + posX[pos];
					short nextY = cur.y + posY[pos];

					if (0 <= nextX && nextX < row && 0 <= nextY && nextY < col && tresureMap[nextX][nextY] != 'W' &&!point[nextX][nextY])
						nextQ.push(Point(nextX, nextY));
				}
			}

			while (!nextQ.empty())
			{
				curQ.push(nextQ.front());
				nextQ.pop();
			}

			++dis;
		}
		if (maxDis < dis)
			maxDis = dis;

	}

	cout << maxDis - 1;

	return 0;
}

2019-01-13 12:00:00에 Tistory에서 작성되었습니다.