최근 풀이 : 240331

: 잘못된 접근 방법

• 조합으로 2개 뽑은 다음에 , 그 2개의 조합정점을 이용해서 bfs 를 하려고 함.
  -> 시간 많이 걸려서 하지 않았는데. 잘못된 생각인듯 하다.

• 그냥 모든 정점 중 L인 부분에 대해 bfs 를 수행하면 될 듯하다.
  딱히 종료 지점없이 진행하자.
  

느낀점

: 너무 생각이 많았따.
조합으로해서 뽑는 것보다도 그냥 bfs로도 처리가 가능하겠구나를 생각했어야 했다.

• 조합으로 진행할 경우
  : 정점의 크기가 5050 이기 때문에 2500 2499 의 시간 복잡도가 bfs에 추가된다.

• 그런데 그냥 모든 정점에 대한 bfs를 진행하면 bfs만의 시간 복잡도로 처리가 가능하기 때문에 조합을 하면 안된다.

---

최근 코드 230115

https://www.acmicpc.net/submit/2589/71743391

• max_element 숙지 필요!

해맨 부분

• 불체크를 어떻게 할것인가?
  : 처음 start pos 인덱스 값 설정에 따라 달라짐..
  http://boj.kr/dca4cf11969a4f08b203028fa5f19167

---

놓친 부분

-1을 해야함...

• 실수한 부분 : 인덱스 뒤바뀜.
  

코드

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

int n, m;

// 상하 좌우 
int dx[]{0,0,-1,1};
int dy[]{ -1,1,0,0 };

int result = 0;

//vector<vector<int>>v;
//vector<vector<bool>>check;
// y가 1번재 쪽 , x가 2번째 쪽
void bfs(int y ,int x , vector<vector<int>>v)
{
	// 그래서 call by value로 진행하자.

	// 임시 변수 하나 만들어서 진행해야 하지 않을까? 
	// 생각됨. 
	vector<vector<bool>>check(v.size(), 
		vector<bool>(v[0].size(), false));
	//check.clear();

	//fill(check.begin(), check.end(), 0);

	queue<pair<int, int>>q;
	q.push(make_pair(y, x));
	check[y][x] = true;
	//v[y][x] = 0;


	while (!q.empty())
	{
		//불변수가 false 인 곳
		// and v 값이 1인 곳만 진입함.
		// => 둘조건 모두 만족시 불변수를 true로 변경함.
		
		int curY = q.front().first;
		int curX = q.front().second;
		q.pop();

		// 아이고 실수... 인덱스 변수 바꿔서 진행함...
		if (result < v[curY][curX])
		{
			result = v[curY][curX];
			//cout << result << endl;
		}

		for (int i = 0; i < 4; i++)
		{
			int nY = curY + dy[i];
			int nX = curX + dx[i];

			if (nY < 0 || nY >= n
				|| nX < 0 || nX >= m)
			{
				continue;
			}
			//cout << q.size() << endl;
			//cout << nY << " " << nX << endl;
			//  v값이 1이어야 만함.
			// check 처리도 해야 함.

			if (v[nY][nX] == 1 && check[nY][nX] == false)
			{
				// 조건 처리 된후, 통과 되면 큐에 추가함.
				q.push(make_pair(nY, nX));
				v[nY][nX] += v[curY][curX];
				check[nY][nX] = true;
			}
			
		}

	}

}


int main() {
	
	// 육지 : l 
	// 바다 : w


	// 육지로만 이동가능함. 

	// 가장 긴 시간이 걸리는 육지

	// 큐로 진행하자. 
	// 하나를 지정해서 모두 돌림
	// for문으로 모두 돌림. 
	// bfs 로 진행하고, 불변수 사용해서 체크 

	// 최대 거리일때 result값을 갱신함.

	cin >> n >> m; 
	
	vector<vector<int>>v(n, vector<int>(m, 0));
	//v.resize(n, vector<int>(m, 0));
	//check.resize(n, vector<bool>(m, 0));
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;

		for (int j = 0; j < m; j++)
		{
			if (s[j] == 'L')
				v[i][j] = 1;
			//else
			// 이미 초기화되어 있음.
		}
	}

	/* 출력하기 
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
	*/

	// L인 부분을 대상으로 전부다 돌려야 함
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (v[i][j] == 1)
			{
				//cout << "wontae" << endl;
				bfs(i, j , v);
			}
		}
	}

	cout << result - 1;
}

-- 그림 설명

: 최종점까지 가는데 , 나의 코드로 하면 9가 나옴.
즉 -1을 반드시 해야함!