백준 14497 주난의 난// bfs멈춰는 큐2개로 해결, 어려우면 1차원에서 논리를 짜라

14497번: 주난의 난(難) (acmicpc.net)

14497번: 주난의 난(難)

* 어려우면 1차원에서 해보면서 논리를 짜라

# 1 0 0 1 0 0 <-사람장풍

0->계속 //q.push

1->멈춰, cnt++ //temp.push, q=temp, cnt++

ex) next가 1일때, temp.push만 되므로 q.size==0이 됨  =>   q=temp, cnt++ 실행됨. //새로운시작

 

* bfs는 도중에 탈출X, 방문배열에 정답을 모두담고, 출력만해라.

 

* 탈출조건 문제 

while (true)
	{
		/*
		* 문제 : 종료조건 ny,nx 접근불가
		* 해결 : 실제로 a[][] 값바꾸기 & 검사
		*/
		if (a[y2][x2] == '0') break;

else if (a[ny][nx] == '1') {
					temp.push({ ny,nx });
					a[ny][nx] = '0';
				}
				else if (a[ny][nx] == '#') {
					temp.push({ ny,nx });
					a[ny][nx] = '0';
				}

 

 

#include <bits/stdc++.h> 
#define MAX 100000
#define y1 aaaaa

using namespace std;
int ret,cnt;
int n, m,y,x,y1,x1,y2,x2,ny,nx,
	dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
int visited[304][304];
char a[304][304];
vector<pair<int, int>> v;

bool in(int a, int b) {
	return 0 <= a && a < n && 0 <= b && b < n;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m>>y1>>x1>>y2>>x2;
	y1--; x1--; y2--; x2--;	//좌표기준을 0,0 으로
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}

	/*
	* bfs algorithm
	* 1.초기화 	cnt[n] = 1;
	* 2.종료조건
	* 3.next 범위체크
	* 4.next 방문체크
	* 5.visit[next] 갱신
	* 5.1 q.push!!
	* 6.추가논리(cnt[next]+=cnt[now])
	*/
	queue<pair<int,int>> q;
	q.push({y1,x1});
	visited[y1][x1] = 1;
	bool flag = 0;
	while (true)
	{
		/*
		* 문제 : 종료조건 ny,nx 접근불가
		* 해결 : 실제로 a[][] 값바꾸기 & 검사
		*/
		if (a[y2][x2] == '0') break;
		queue<pair<int, int>> temp;
		cnt++;

		while (q.size())
		{
			tie(y, x) = q.front(); q.pop();
			for (int i = 0; i < 4; ++i) {
				//1. 범위체크
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (!in(ny, nx)) continue;
				if (visited[ny][nx]) continue;
				//if (a[ny][nx] == '0') continue;
				visited[ny][nx] = cnt;
				if (a[ny][nx] == '0') {
					q.push({ ny,nx });
				}
				else if (a[ny][nx] == '1') {
					temp.push({ ny,nx });
					a[ny][nx] = '0';
				}
				else if (a[ny][nx] == '#') {
					temp.push({ ny,nx });
					a[ny][nx] = '0';
				}
			}
		}
		q = temp;
	}
	

	cout << visited[y2][x2];

}
/*
5 17
 */