백준 2589 : 보물섬

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

1. 접근

• 결국 가장 먼 두 지점을 구하는 문제이고, "가장" 긴 거리를 구하는 문제에는 BFS가 가장 적절하다. (한번에 한단계씩 이동하기때문에 가장 길거나, 가장 짧은 거리를 구할 때에는 BFS가 더 적절하다)
• 초기 지도를 입력받고, 그 지도의 값을 BFS로 1씩 더해주면서 가장 큰 값을 택하면 된다.
• 전체 변수 값이 작기 때문에 모든 L 값에 대해 BFS를 구해주었다. 입장할때마다 초기 지도값을 복사해주었다.

+2차원 배열 복사는 copy를 이용했다.
+초기 카운트값을 0으로 설정하고 풀었었는데, 0으로 하면 다른 케이스가 들어가서 오답이 된다고 해서, 1로 설정하고 마지막에 1을 빼주었다. 아마 초기 카운트와 그냥 L값을 구분하기 어려워서 그런것같다.

2. 나의 풀이

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

int n, m;
int map[51][51];
int input[51][51];
bool visited[51][51];
int maxval = 0;
int dc[4] = { -1,1,0,0 };
int dr[4] = { 0,0,-1,1 };

void BFS(int x, int y) {
	queue<pair<pair<int, int>, int>> q;
	q.push(make_pair(make_pair(x, y), 1));
	visited[x][y] = true;

	while (!q.empty()) {
		int c = q.front().first.first;
		int r = q.front().first.second;
		int count = q.front().second;
		q.pop();
		if (count > maxval)	maxval = count;

		for (int i = 0; i < 4; i++) {
			int nc = c + dc[i];
			int nr = r + dr[i];
			if (nc >= 0 && nc < n && nr>=0 && nr < m) {
				if (map[nc][nr] ==0&&!visited[nc][nr]) {
					q.push(make_pair(make_pair(nc, nr), count + 1));
					map[nc][nr] = count + 1;
					visited[nc][nr] = true;
				}
			}
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string tem;
		cin >> tem;
		for (int j = 0; j < m; j++) {
			if (tem[j] == 'W')	input[i][j] = -1;
			else if (tem[j] == 0)	input[i][j] = 0;
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (input[i][j]==0) {
				copy(&input[0][0], &input[0][0] + 51*51, &map[0][0]);
				memset(visited, false, sizeof(visited));

				BFS(i, j);
			}
		}
	}

	cout << maxval-1<< "\n";
	return 0;
}