14497 - 주난의 난

문제

14497번: 주난의 난

코드

#include <bits/stdc++.h>
using namespace std;

int n,m,x1,x2,yf,y2,ret;
pair<int,int> b;
char a[304][304];
int visited[304][304];
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};
queue<pair<int,int>> tq;

void solve(int y, int x){
	queue<pair<int,int>> q;
	visited[y][x] = 1;
	q.push({y,x});
	
	while(a[y2][x2] != '0'){
		ret++;
		
		while(q.size()){
		b = q.front();
		q.pop();
		for(int i = 0; i < 4; i++){
			int ny = b.first + dy[i];
			int nx = b.second + dx[i];
			if(ny < 1 || ny > n || nx < 1 || nx > m || visited[ny][nx]) continue;
			visited[ny][nx] = ret;
			if(a[ny][nx] != '0'){
				a[ny][nx] = '0';
				tq.push({ny,nx});
			}else q.push({ny,nx});
		}
	}
	q = tq;
}
	cout << visited[y2][x2] << '\n';	
}

int main(){
	cin >> n >> m;
	cin >> yf >> x1 >> y2 >> x2;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	solve(yf, x1);
	return 0;
}

풀이

우선 왜 y1이라는 변수가 사용 안되는지는 모르겠지만 사용이 안되길래 yf라는 뜬금없는 변수를 사용하긴했다.
문제 이해가 가장 어려웠는데 상,하,좌,우 중 1을 만나지 않으면 다시 상,하,좌,우로 뻗어나간다. 즉, 도착점 'y2,x2'에 도착하기 전까지 0을 만나면 BFS를 해야한다.
근데 그 0을 기점으로 한 BFS는 1을 기점으로 멈춰야한다. --> 아래 사진으로 간단하게 설명해봤다.

큰 루프는 끝점을 만나기 전이다.
그런데 0을 만난 점도 1에서 멈춰야하기 때문에
while 2개를 중첩시켜서 간다.
큰 루프 입장에서는 1을 만났을 때 ret을 올리는게 중요하니까 메인 queue에는 1을 만났을 때를 담는다.
작은 루프는 0을 만났을 때 새로운 queue를 담아서 큰 루프에 지장없게 움직인다.

결과

후기

하 이게 골드 4라는게 믿기지가 않는다.
너무 틀에 박힌 생각대로 푸려다가 머리 깨질뻔했다.