[BOJ] 2589번 보물섬(C++)

풀이 소요시간 : 25분

잠시 DFS로 접근해야 하나 생각하다가 하자가 있다는 것을 깨닫고 BFS로 접근했다.
큰 어려움 없이 한번에 풀어내는데 성공했다. 앞으로도 정밀하게 코드 짜는걸 연습하자.

전체 코드

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

int N, M;
char Map[51][51];
int Visit[51][51];

int Max = 0;
struct Position {
	int x;
	int y;
	int dist;
};
queue<Position> Q;

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


void Clear() {
	memset(Visit, 0, sizeof(Visit));
}

void Input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> Map[i][j];
		}
	}
}

void Bfs() {
	while (!Q.empty()) {
		int px = Q.front().x;
		int py = Q.front().y;
		int dist = Q.front().dist;
		Q.pop();

		Max = max(Max, dist); // 최대거리 갱신
		for (int i = 0; i < 4; i++) {
			int nx = px + dx[i];
			int ny = py + dy[i];
			
			if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
			if (Visit[nx][ny] == 1 || Map[nx][ny] == 'W') continue;

			Visit[nx][ny] = 1;
			Q.push({ nx, ny, dist + 1 });
		}	
	}
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	Input();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (Map[i][j] == 'L') {
				Q.push({ i, j, 0 });
				Visit[i][j] = 1;
				Bfs();
				Clear();
			}
		}
	} cout << Max << '\n';

}