최근 접근 방법 241130

• 굳이 지훈이 bfs 하는 것과 불전체에 대해 bfs 하는 거를 동시에 할 필요가 없다.
  : 지훈이 진행하면서 갱신하고, 불 전체에 대해 탐색하면서 진행하기에는 코드가 복잡해진다....

https://www.acmicpc.net/submit/4179/87026900

• 생각해보자.
  1) 불 F에 대해 2차원 벡터 fireTable에 대해 최단 거리를 기록한다.
  2) 지훈이 F에 대해 2차원 벡터 jihoonTable에 대한 최단 거리를 기록한다.
  3) 1과 2에서 구한 2개의 table을 비교하는 시퀀스로 진행하고, 지훈이가 테두리에 도착한 table값이 firetable보다 작다면 미로 탈출이 가능하다.

---

최근풀이 : 240404 틀림

• 참고 사이트
  https://cloer.tistory.com/136

전략

• 틀린 생각
  : 문제를 풀 때 나는 지훈이 bfs 처리 후, 불 bfs 이동하려고 했는데
  이런식으로 하기에는 각 큐 2개를 만들어서 처리해야 하는데,
  시퀀스 작성을 어떻게 할 것인가에 대한 문제가 있다.

• 큰돌님 강의를 본후 전략 수정
  : 어쨋든 지훈이는 테두리를 향해서 탈출하려고 하는데, 각 정점의 최단거리로 향하는 것과
  불이 해당 정점으로 번져나가는 최단 거리를 비교하는 방식으로 하면
  지훈이가 미로를 통과가능한 것인가에 대한 논리적인 생각을 할 수 있다.

올바른 접근 예시.

• 지훈이가 이동할수 있는 각 정점의 최단 거리는 이렇다.
  

• 그러면 불의 각 정점에서의 최단경로는?
  

• 지훈이의 빨간 최단거리과 불의 파란 최단 경로는 비교하면
  : 테두리를 통해 통과해야 하므로, 지훈이는 좌측 하단의 2를 통해
  미로를 탈출할 수 있다.

• 지훈이의 입장에서 3에 해당하는 정점이 불의 입장에서 보면, 2이기 때문에
  3으로는 절대 통과할 수 없다. 불에 타 죽음...

-> 이거를 염두하고 코드를 작성하면 된다.
: 여기서 생각할 수 있는 부분은 불을 먼저 확상해서 파란색숫자대로
저장을 해놓고, 빨간색 3은 진행할 필요가 없다. 해당 정점은 불의 경로보다
더 길기 때문에

---

알고리즘 분류

: bfs

풀이법 : 문제에서 주어지지 않았찌만,
불을 먼저 이동하고, 지훈이를 이동시켜야 함.
맨 밑에 반례 있음.
https://www.acmicpc.net/board/view/63687

내가 만든 코드대로 하면 탈출을 하게 되는데/

RESULT : 이때 지훈이는 탈출을 못해야 함.

왜 탈출을 못해야 하냐면?
논리적으로 생각하면, '.' 이있는 부분에 불과 지훈이가 모두 올수 있음.
그럼 지훈이는 탈출을 못하게 되는 상황임.
따라서 불을 먼저 이동해야 하는 프로세스 맞음.

첫번째 코드

-> 58퍼센트 에서 틀림.

현재 지훈이를 먼저 이동한 후에, 불을 이동시켰음..
이제 문제가 아니다.

#include <iostream>
#include <vector>
using namespace std;
#include <algorithm>
#include <queue>
#include <string>
// 15:50

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

int n, m;
// 지훈이가 먼저 이동해야 함.
// 지훈이는 불이 아닌 곳, 벽이 아닌곳, 으로만 움직일 수 있고,
// 지훈이는 미로 가장자리에서 탈출이 가능함. 탈출할때의 최단 시간을 
// 알아야 함.
void bfs(vector<vector<char>>&v, vector<vector<bool>>&_check,
	pair<int,int>&_jh, vector<pair<int,int>>&f)
{
	//벽은 변하지 않음.
	// 추가되지도 않음.

	// . 공간은 불이 될 수 있음.

	queue < pair<pair<int, int> , int> >qF;
	for (auto iter : f)
	{
		qF.push(make_pair(make_pair(iter.first, iter.second), 0));
	}

	queue<pair<pair<int, int> , int>>pos;
	pos.push(make_pair(make_pair(_jh.first, _jh.second), 0));
	_check[_jh.first][_jh.second] = true;

	// 지훈이가 이동완료된 부분은 체크불변수를 사용해야 함.

	while (!pos.empty())
	{
		int curY = pos.front().first.first;
		int curX = pos.front().first.second;
		int cnt = pos.front().second;
		
		pos.pop();

		// 만약에 지훈이가 테두리 도착시 그냥 끝.
		if (curY == 0 || curY == n -1
			|| curX == 0 || curX == m - 1)
		{
			cout << cnt + 1;
			return;
		}

		


		// 지훈이가 있던 위치는 . 으로 변경해야 함.
		v[curY][curX] = '.';

		// 지훈이 이동 부터.
		for (int i = 0; i < 4; ++i)
		{
			int nextY = curY + dy[i];
			int nextX = curX + dx[i];

			//테두리 확인
			if (nextY < 0 || nextY >= n
				|| nextX < 0 || nextX >= m)			
				continue;			
			// 벽 확인 
			if (v[nextY][nextX] == '#' 
				|| v[nextY][nextX] == 'F')
				continue;
			
			// 이동할수 있는 부분을 불체크
			if (_check[nextY][nextX] == true)
				continue;

			// 지나갈수 있는 공간일 경우에 이동함
			if (v[nextY][nextX] == '.')
			{
				pos.push(make_pair(make_pair(nextY, nextX),
					cnt + 1));
				_check[nextY][nextX] = true;
			}
		}

		// 불 확산을 해야함. 
		
		// 일단 qF에 있는 것들을 확산해야 함.
		// 2번째 인자에 있는 값을 통해서만 확산 완료
		// 그 이후에는 뛰쳐 나와야 함.
		while (!qF.empty())
		{
			// 카운팅 횟수와 비교해서 일치한 카운트만 돌려야 함.
			int cntF = qF.front().second;
			if (cnt != cntF)
				break;

			int curFY = qF.front().first.first;
			int curFX = qF.front().first.second;

			qF.pop();

			// 불확산.
			for (int i = 0; i < 4; ++i)
			{
				int nextFY = curFY + dy[i];
				int nextFX = curFX + dx[i];

				//테두리 확인
				if (nextFY < 0 || nextFY >= n
					|| nextFX < 0 || nextFX >= m)
					continue;
				// 벽 확인 
				if (v[nextFY][nextFX] == '#'
					|| v[nextFY][nextFX] == 'F')
					continue;

				// 벽 아니고, 불이 아닌 부분을 불로 만들어 버림.
				
				v[nextFY][nextFX] = 'F';
				qF.push(make_pair(make_pair(nextFY, nextFX), cntF + 1));

			}


		}



	}

	// 지훈이가 탈출할 수 없을때 생각해야 함.
	cout << "IMPOSSIBLE";


}

int main() 
{
	// 미로의 가장자리가 탈출 공간임.

	// 불과 지훈이 1초마다 이동함.
	// 불을 먼저 확산해야 함.

	
	cin >> n >> m;

	vector<vector<char>>v(n, vector<char>(m));

	//지훈이의 초기 위치
	// 불의 초기 위치
	pair<int, int>jihoon;
	vector<pair<int, int>>fire;

	// 지훈이가 이동완료 여부를 체크하는 불변수
	vector<vector<bool>>check(n, vector<bool>(m));

	for (int i = 0; i < n; ++i)
	{
		string word;
		cin >> word;

		for (int j = 0; j < m; ++j)
		{
			v[i][j] = word[j];

			if (v[i][j] == 'J')
			{
				jihoon.first = i;
				jihoon.second = j;
			}

			if (v[i][j] == 'F')
			{
				fire.push_back(make_pair(i, j));
			}
		}
	}

	//cout << jihoon.first << ' ' << jihoon.second << endl;
	//
	//for (auto iter : fire)
	//{
	//	cout << iter.first << ' ' << iter.second << endl;
	//}
	bfs(v, check, jihoon, fire);
}

완료 코드

#include <iostream>
#include <vector>
using namespace std;
#include <algorithm>
#include <queue>
#include <string>
// 15:50

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

int n, m;
// 지훈이가 먼저 이동해야 함.
// 지훈이는 불이 아닌 곳, 벽이 아닌곳, 으로만 움직일 수 있고,
// 지훈이는 미로 가장자리에서 탈출이 가능함. 탈출할때의 최단 시간을 
// 알아야 함.
void bfs(vector<vector<char>>&v, vector<vector<bool>>&_check,
	pair<int,int>&_jh, vector<pair<int,int>>&f)
{
	//벽은 변하지 않음.
	// 추가되지도 않음.

	// . 공간은 불이 될 수 있음.

	queue < pair<pair<int, int> , int> >qF;
	for (auto iter : f)
	{
		qF.push(make_pair(make_pair(iter.first, iter.second), 0));
	}

	queue<pair<pair<int, int> , int>>pos;
	pos.push(make_pair(make_pair(_jh.first, _jh.second), 0));
	_check[_jh.first][_jh.second] = true;

	// 지훈이가 이동완료된 부분은 체크불변수를 사용해야 함.

	while (!pos.empty())
	{
		int curY = pos.front().first.first;
		int curX = pos.front().first.second;
		int cnt = pos.front().second;
		// 불 확산을 해야함. 
		
		// 일단 qF에 있는 것들을 확산해야 함.
		// 2번째 인자에 있는 값을 통해서만 확산 완료
		// 그 이후에는 뛰쳐 나와야 함.
		while (!qF.empty())
		{
			// 카운팅 횟수와 비교해서 일치한 카운트만 돌려야 함.
			int cntF = qF.front().second;
			if (cnt != cntF)
				break;

			int curFY = qF.front().first.first;
			int curFX = qF.front().first.second;

			qF.pop();

			// 불확산.
			for (int i = 0; i < 4; ++i)
			{
				int nextFY = curFY + dy[i];
				int nextFX = curFX + dx[i];

				//테두리 확인
				if (nextFY < 0 || nextFY >= n
					|| nextFX < 0 || nextFX >= m)
					continue;
				// 벽 확인 
				if (v[nextFY][nextFX] == '#'
					|| v[nextFY][nextFX] == 'F')
					continue;

				// 벽 아니고, 불이 아닌 부분을 불로 만들어 버림.
				
				v[nextFY][nextFX] = 'F';
				qF.push(make_pair(make_pair(nextFY, nextFX), cntF + 1));

			}


		}

		// 여기로 옮김
		pos.pop();

		// 만약에 지훈이가 테두리 도착시 그냥 끝.
		if (curY == 0 || curY == n - 1
			|| curX == 0 || curX == m - 1)
		{
			cout << cnt + 1;
			return;
		}




		// 지훈이가 있던 위치는 . 으로 변경해야 함.
		v[curY][curX] = '.';

		// 지훈이 이동 부터.
		for (int i = 0; i < 4; ++i)
		{
			int nextY = curY + dy[i];
			int nextX = curX + dx[i];

			//테두리 확인
			if (nextY < 0 || nextY >= n
				|| nextX < 0 || nextX >= m)
				continue;
			// 벽 확인 
			if (v[nextY][nextX] == '#'
				|| v[nextY][nextX] == 'F')
				continue;

			// 이동할수 있는 부분을 불체크
			if (_check[nextY][nextX] == true)
				continue;

			// 지나갈수 있는 공간일 경우에 이동함
			if (v[nextY][nextX] == '.')
			{
				pos.push(make_pair(make_pair(nextY, nextX),
					cnt + 1));
				_check[nextY][nextX] = true;
			}
		}


	}

	// 지훈이가 탈출할 수 없을때 생각해야 함.
	cout << "IMPOSSIBLE";


}

int main() 
{
	// 미로의 가장자리가 탈출 공간임.

	// 불과 지훈이 1초마다 이동함.
	// 불을 먼저 확산해야 함.

	
	cin >> n >> m;

	vector<vector<char>>v(n, vector<char>(m));

	//지훈이의 초기 위치
	// 불의 초기 위치
	pair<int, int>jihoon;
	vector<pair<int, int>>fire;

	// 지훈이가 이동완료 여부를 체크하는 불변수
	vector<vector<bool>>check(n, vector<bool>(m));

	for (int i = 0; i < n; ++i)
	{
		string word;
		cin >> word;

		for (int j = 0; j < m; ++j)
		{
			v[i][j] = word[j];

			if (v[i][j] == 'J')
			{
				jihoon.first = i;
				jihoon.second = j;
			}

			if (v[i][j] == 'F')
			{
				fire.push_back(make_pair(i, j));
			}
		}
	}

	//cout << jihoon.first << ' ' << jihoon.second << endl;
	//
	//for (auto iter : fire)
	//{
	//	cout << iter.first << ' ' << iter.second << endl;
	//}
	bfs(v, check, jihoon, fire);
}