Baekjoon2589-보물섬

백준 사이트 2589 - 보물섬 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

bfs문제입니다.
기존 bfs와 달리 변수 하나를 더 저장하면 쉽게 풀 수 있습니다. 백준에서는 Gold5난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 변수 하나를 더 저장하기 위해 pair를 두 개 겹쳐 썼습니다.
• 마지막에 카운트 값을 비교하기위해 count라는 변수를 함수의 지역변수로 선언했습니다. (값이 사라지지 않기 위하여)

---

5. code

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>

const int MAX = 51;

char MAP[MAX][MAX] = { '0', };
bool v[MAX][MAX] = { false, };

using namespace std;

int row, col;
int result = 0;

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

void Input()
{
	scanf("%d %d", &row, &col);
	getchar();
	for (int i = 0; i < row; ++i)
	{
		for (int j = 0; j < col; ++j)
			scanf("%1c", &MAP[i][j]);
		getchar();
	}
}

void BFS(int x, int y)
{
	memset(v, false, sizeof(v));
	queue<pair<pair<int, int>, int>> q;//첫번째와 두번째는 좌표 값, 세번째는 거리

	q.push(make_pair(make_pair(x, y), 0));
	v[x][y] = true;
	int count = 0;
	while (!q.empty())
	{
		int x = q.front().first.first;
		int y = q.front().first.second;
		count = q.front().second;
		q.pop();
		for (int k = 0; k < 4; ++k)
		{
			int newX = x + dx[k];
			int newY = y + dy[k];
			if (0 <= newX && newX < row && 0 <= newY && newY < col && v[newX][newY] == false && MAP[newX][newY] == 'L')
			{
				q.push(make_pair(make_pair(newX, newY), count + 1));
				v[newX][newY] = true;
			}
		}
	}
	//비교문
	if (result < count)
		result = count;

}

void Solve()
{
	for (int i = 0; i < row; ++i)
	{
		for (int j = 0; j < col; ++j)
		{
			if (MAP[i][j] == 'L')
				BFS(i, j);
		}
	}
	printf("%d", result);
}

int main()
{
	Input();
	Solve();
}

---

6. 후기

원큐 성공.