언제 큐를 2개 사용할 것인가?

원소의 상태값이 2개다 라고 한다면, 큐를 2개 사용해볼까? 라는 생각을 하자.

• 1) 고정된 위치에서 탐색을 하는 것보다, 변경된 위치에서 탐색하는 것이 효율적일 경우

• 2) 큐에 넣는 횟수가 pop하는 횟수보다 더 많은데, 추가적으로 상태가 변경된 원소의 인덱스를 넣어야 할 경우.

큐를 왜 2개 사용해야 하는 것인가?

1. 효율적으로 동작시키기

: 주난이의 위치가 현재 고정되어 있음.
'#' 을 만날때 동안 고정된 위치에서 점프를 계속하는 것은
이미 방문한 지점을 또 방문하게 되는 것임.
그래서 1을 만나게 되면, 여기서부터 재시작 하라는 의미임.
이런식으로 해야 범인을 잡는데 훨씬 용이함.
0인 경우에 계속해서 1을 만날때까지 진행하는 것이고,
1을 temp에 넣어 놓고, 해당 temp를 이용해서 재시작!
이렇게 되면, 주난이의 위치보다 더 멀리 바깥으로 퍼지게 됨.
범인을 잡는데 훨씬 좋음.

• 백조와 호수와 동일한 유형의 문제임.

2. 메모리 문제.

• 하나의 큐에다가 넣어도 되지만, 메모리 이슈가 생김.

  : 아래에서처럼 하나만 넣어도 40바이트를 차지하고 있는데,
  0이 많은 부분에서 또 1이 있는 원소의 위치를 넣는 것은 효율적이지 않음.
  이렇게 되면, 끝없이 계속 큐의 메모리가 쌓이게 됨.
  왜냐 하면 끝에 범인이 있을 경우, 큐가 pop하는 것보다 0,1 원소의 인덱스를
  push하는 횟수가 더 많아지기 때문이다.
  
  -예시에서는 0과 1의 개수가 많지 않지만, 범인이 저 끝에 있으면, 큐의 메모리 어마어마 해짐..

• pair를 넣었을 때 큐의 메모리는?
  : 한개만 넣었는데도 메모리가 생각보다 큼. : 8바이트 하지 않을까???
  

0을 만나면 1을 만날때까지 계속해서 큐 푸쉬 팝 작업을 하게 됨.
그러다가 1을 만난 상태에서 0을 만들고, 또 삽입을 하게될 경우,
큐 메모리가 커지게됨.

언제품?

: 220911 15:43 ~ 16:41

• 1. 동일한 큐에다가 넣고 제출했는데, 7퍼센트에서 틀림.
• 2. 당황하지 말고, 상태값에 따라 큐를 분리해서 처리하는 방식으로 하면됨.

알고리즘 분류

: bfs, 특이한 문제, 레벨 분류로 인한 큐 2개 사용

어떻게 접근할 것인가?

문제 맨 처음 접했을 때

1) 문제를 읽어 봤을 때, 주난이가 1을 만나면, 1 -> 0으로 변경을 함.
2) 그리고 카운팅을 1증가함.
3) 그리고 다시 또 들어가서 큐에다가 돌리면서 1만나면,
또 뛰쳐나와서 카운팅을 1증가할까? 라는 생각을 하게됨.

1. 다른 고찰

1) 위의 생각대로 해도 되지만, 0이든, 1이든 그냥
큐에다가 한번에 넣어서 처리해도 되지 않을까? 생각을 하게 됨.

• 결과 : 큐에 엄청 들어가서 메모리 터지는 듯함.

2. 다른 고찰

1) 현재 1인 경우와 0인 경우, 즉 레벨이 다름.
2) 레벨을 구분으로 해서 다른 큐로 나뉘어서 진행하자.
3) 추가적으로 계속 돌리기 위해 , while(1) 을 추가함.

완료 풀이

#include <algorithm>
#include <string>
#include <vector>
#include<iostream>
#include <queue>

using namespace std;

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

int n, m;
int x, y, x2, y2;


void bfs(vector<vector<char>>&v,
	vector<vector<int>>&visited)
{
	// 원소의 타입은 char형임. 

	//불변수의 값을 통해서 몇번의 카운팅으로 
	// #에 도달했는지를 확인하자. 

	queue<pair<int, int>>q;

	// 내가 입력한 값의 -1씩 해야 함.
	q.push(make_pair(y - 1, x - 1));

	visited[y - 1][x - 1] = 1;

	queue<pair<int, int>> temp;


	//while (v[y2 - 1][x2 - 1] != '0')
    // 위의 무한문은 생각하지 못할 수 있음. 
	while (1)
	{
		while (!q.empty())
		{
			int curY = q.front().first;
			int curX = q.front().second;

			q.pop();

			//visited[curY][curX] = 1;

			if (v[curY][curX] == '#')
			{
				cout << visited[curY][curX];
				return;
			}

			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 (visited[nextY][nextX] != 0)
					continue;

				// v의 원소가 0인 경우와 1인 경우가 다름. 
				// 내 생각에서는 0인 경우에는 카운팅을 하지 말고.
				// 1인 경우에만 카운팅을 함. 
				if (v[nextY][nextX] == '1')
				{
					v[nextY][nextX] = '0';
					visited[nextY][nextX] = visited[curY][curX] + 1;
					//q.push(make_pair(nextY, nextX));
					temp.push(make_pair(nextY, nextX));
				}
				else if (v[nextY][nextX] == '0')
				{
					visited[nextY][nextX] = visited[curY][curX];
					q.push(make_pair(nextY, nextX));

				}
				else if (v[nextY][nextX] == '#')
				{
					visited[nextY][nextX] = visited[curY][curX];
					q.push(make_pair(nextY, nextX));
				}

			}
		}
		q = temp;
	}


}





//20: 53 ~ 21:51
// 7퍼센트에서 틀림.
int main()
{
	//1인 원소들을 0으로 변경함. 

	// 1인 원소를 찾으면 카운팅을 진행함. 

	// 인접한 것들 중에 0인 원소를 만나면, 카운팅은 안함. 

	cin >> n >> m;
	cin >> y >> x >> y2 >> x2;

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


	for (int i = 0; i < n; ++i)
	{
		string ss;
		cin >> ss;
		for (int j = 0; j < m; ++j)
		{
			v[i][j] = ss[j];
		}
	}

	bfs(v, visited);



}

재풀이

: 13:29 ~ 13:42

맞왜틀

: 큐에다가 마구 넣어서 메모리 초과된 듯 함.

문제풀이

: 만약 시간 초과가 발생한다고 한다면?
-> int형 하나만으로 접근하는 것에 대해서 생각을 해보자.
지금 문제가 이러한 유형임.
y 값, x값에 대해서 하나의 축에 * 1000 또는 특정 거대한 값을 더하고,
다른 축은 그냥 더하는 방법으로 .

• 최대 범위보다 좀 더 큰 값을 기반으로 해서 접근해야 함.

첫번째 풀이

: 7퍼센트에서 틀림.
-> 아무래도 메모리 초과한듯 함..

#include <algorithm>
#include <string>
#include <vector>
#include<iostream>
#include <queue>

using namespace std;

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

int n, m;
int x, y, x2, y2;


void bfs(vector<vector<char>>&v,
	vector<vector<int>>&visited)
{
	// 원소의 타입은 char형임. 

	//불변수의 값을 통해서 몇번의 카운팅으로 
	// #에 도달했는지를 확인하자. 

	queue<pair<int, int>>q;

	// 내가 입력한 값의 -1씩 해야 함.
	q.push(make_pair(y - 1, x - 1));

	visited[y - 1][x - 1] = 1;

	while (!q.empty())
	{
		int curY = q.front().first;
		int curX = q.front().second;

		q.pop();

		//visited[curY][curX] = 1;

		if (v[curY][curX] == '#')
		{
			cout << visited[curY][curX];
			return;
		}

		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 (visited[nextY][nextX] != 0)
				continue;

			// v의 원소가 0인 경우와 1인 경우가 다름. 
			// 내 생각에서는 0인 경우에는 카운팅을 하지 말고.
			// 1인 경우에만 카운팅을 함. 
			if (v[nextY][nextX] == '1')
			{
				visited[nextY][nextX] = visited[curY][curX] + 1;
				q.push(make_pair(nextY, nextX));
			}
			else if (v[nextY][nextX] == '0')
			{
				visited[nextY][nextX] = visited[curY][curX];
				q.push(make_pair(nextY, nextX));

			}
			else if (v[nextY][nextX] == '#')
			{
				visited[nextY][nextX] = visited[curY][curX];
				q.push(make_pair(nextY, nextX));
			}

		}



	}


	cout << "hello" << endl;

}





//20: 53 ~ 21:51
// 7퍼센트에서 틀림.
int main()
{
	//1인 원소들을 0으로 변경함. 

	// 1인 원소를 찾으면 카운팅을 진행함. 

	// 인접한 것들 중에 0인 원소를 만나면, 카운팅은 안함. 

	cin >> n >> m;
	cin >> y >> x >> y2 >> x2;

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


	for (int i = 0; i < n; ++i)
	{
		string ss;
		cin >> ss;
		for (int j = 0; j < m; ++j)
		{
			v[i][j] = ss[j];
		}
	}

	bfs(v, visited);



}