BFS 보물섬 코드

여기서의 point 는 결국 for loop 두개를 돌리듯이 

queue 를 두개 사용해서 L 에 관련해서  for loop 을 두번 돌리는게 핵심 접근 방법 

그리고  더 짧은 경로가 있을지 모르니 짧은 경로일 경우 추가하는..  point  를 넣어 주는 게 핵심 

if (!dist[ny][nx] || dist[ny][nx] > dist[y][x] + 1){

dist[ny][nx] = dist[y][x] + 1;
q.push(make_pair(nx, ny));
}
#include <stdio.h>
#include <iostream> 
#include <vector>
#include <cmath>
#include <string>
#include <set>
#include <queue>
#include <functional>
#include <algorithm>
#include <memory.h>


#pragma warning(disable : 4996)
using namespace std;


long long min_v, max_v;


#define MAX(a,b) a>b ? a:b
#define MIN(a,b) a>b ? b:a
#define MAX_VAL 100001
vector<vector<int> > adj; // 인접리스트
vector<bool> discovered; // 발견 여부 체크
int V, S, E;
int M, N;


vector<bool>  discov;
queue < pair <int, int >> q;


int ans = 0;




char map[301][301];
int dist[301][301];


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








int main() {


	int TC = 1;
	int MAX_SIZE;


	freopen("input12.txt", "r", stdin);	setbuf(stdout, NULL);   //cin >> TC;


	


	cin >> M >> N;
	queue<pair<int, int> > land;


	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'L'){
				land.push(make_pair(j, i));
			}
		}
	}




	while (!land.empty()){


		memset(dist, 0, sizeof(dist));




		int land_x = land.front().first;
		int land_y = land.front().second;
		dist[land_y][land_x] = 1;
		


		land.pop();
		queue<pair<int, int> > q;


		q.push(make_pair(land_x, land_y));


		while (!q.empty()){


			int x = q.front().first;
			int y = q.front().second;


			


			q.pop();
			for (int k = 0; k < 4; k++){


				int nx = x + dx[k];
				int ny = y + dy[k];


				if (0 > nx || nx >= N || 0 > ny || ny >= M)
					continue;


				//if (map[ny][nx] == 'W' || (land_x == nx && land_y == ny))
				if (map[ny][nx] == 'W')
					continue;


				if (!dist[ny][nx] || dist[ny][nx] > dist[y][x] + 1){
					dist[ny][nx] = dist[y][x] + 1;
					q.push(make_pair(nx, ny));
				}


			}


		}


		for (int i = 0; i<M; i++)
			for (int j = 0; j<N; j++)
				if (dist[i][j])
					ans = max(ans, dist[i][j]);
	}


	
	
	cout << ans -1 << endl;


	return 0;
}