백준 5427 불 (bfs)

https://www.acmicpc.net/problem/5427

5427번: 불

#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <queue>

using namespace std;

int w, h;
char map[1002][1002];
int visited[1002][1002];
int tc;
queue <pair<int, int>> q;
queue <pair<pair<int, int>, int>> q2;
int fireSize;
int personSize;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int ans;

void initAll() {
	for (int i = 0; i < 1002; i++) {
		for (int j = 0; j < 1002; j++) {
			map[j][i] = '.';
			visited[j][i] = 0;
		}
	}
}
void moving() {
	while (1) {
		fireSize = q.size();
		while (fireSize--) {

			int x = q.front().first;
			int y = q.front().second;
			q.pop();

			for (int i = 0; i < 4; i++) {
				int cx = x + dx[i];
				int cy = y + dy[i];

				if (map[cx][cy] == '.' && cx < w && cy < h && cx >= 0 && cy >= 0) {
					map[cx][cy] = '*';
					q.push(make_pair(cx, cy));
				}
			}
		}
		personSize = q2.size();
		while (personSize--) {
			int x = q2.front().first.first;
			int y = q2.front().first.second;
			int cnt = q2.front().second;
			q2.pop();

			if ((x == w - 1 || y == h - 1 || x == 0 || y == 0)) {
				//하나라도 끝이라면?
				if (cnt < ans) {
					ans = cnt;
					//break;
				}
			}
			for (int i = 0; i < 4; i++) {
				int cx = x + dx[i];
				int cy = y + dy[i];

				if (map[cx][cy] == '*' || map[cx][cy] == '#') continue;
				else if (map[cx][cy] == '.' && cx < w && cy < h && cx >= 0 && cy >= 0 && visited[cx][cy] == 0) {
					visited[cx][cy] = 1;
					q2.push(make_pair(make_pair(cx, cy), cnt + 1));
				}

			}

		}

		if (q2.empty() && q.empty()) {
			while (!q.empty()) {
				q.pop();
			}
			break;
		}

	}

}
int main() {

	scanf_s("%d", &tc);
	for (int t = 0; t < tc; t++) {
		ans = 987654321;
		fireSize = 0;
		personSize = 0;
		initAll();

		scanf_s("%d%d", &w, &h);
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> map[j][i];
				visited[j][i] = 0;
				if (map[j][i] == '*') {
					q.push(make_pair(j, i));
				}
				else if (map[j][i] == '@') {
					q2.push(make_pair(make_pair(j, i), 0));
				}
			}
		}

		moving();

		if (ans == 987654321) 
			cout << "IMPOSSIBLE" << endl;
		else 
			cout << ans + 1 << endl;

	}
	return 0;
}

 

	if ((x == w - 1 || y == h - 1 || x == 0 || y == 0)) {
				//하나라도 끝이라면?
				if (cnt < ans) {
					ans = cnt;
					//break;
				}
			}

이 부분에서 엄청 헤맸습니다. 

 

if (map[x][y] = '.' && (x == w - 1 || y == h - 1 || x == 0 || y == 0)) {}

했기 때문 ..... 

 

이러면 

 

.

@

.

일때 답이 2가 나온다. 원래는 1인데..  '.'일 경우만 움직이기 때문에 위아래로 밖에 못움직인다. 

 

후..... 오랬동안 풀었네