백준 5427

1. 문제이해
매초마다 불은 상하좌우 빈공간으로 이동
상근이도 매초마다 상하좌우로 이동 가능 벽쪽으로 이동 X, 불이 있는 칸 또는 이제 불이 붙으려는 칸으로 이동 X
빌딩을 탈출하기 위한 최소 시간을 구하기

2. 문제분석

지도(board), 불이동시간(fireMoveT), 상근이 이동시간(playerMoveT) 총 3개의 배열 필요
불이붙는 이동시간을 계산할때 불이 최초에 있는 지점은 0초이고 0이상인 경우 불이 있는 곳이기 때문에 체크 X

상근이의 이동시간(PT)이 불이 붙는시간(FT)보다 무조건 작아야지 이동가능

- 지도에 불과 상근이의 위치를 나타내면서 불이 있는 모든 위치를 큐에 넣음
- 큐를 통해서 지도 전체에 불이 붙는 시간을 모두 계산함

- 상근이의 시작위치를 큐에 넣음
- 상근이가 이동하면서 FT와 비교하면서 이동가능한 거리 계산
- map을 빠져나가는 경우 최소시간 출력

 

3. 코드

#include<iostream>
#include<queue>	
using namespace std;

char board[1001][1001];
int fireMoveT[1001][1001];
int playerMoveT[1001][1001];

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	// 1.입력
	int T;
	cin >> T;

	while (T--) {
		int w, h; // w(열), h(행)
		cin >> w >> h;

		// fireMoveT, playerMoveT 초기화
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				fireMoveT[i][j] = -1;
				playerMoveT[i][j] = -1;
			}
		}

		queue<pair<int, int>> Q1; // 불 위치
		queue<pair<int, int>> Q2; // 상근이 위치
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> board[i][j];				
				if (board[i][j] == '*') {
					fireMoveT[i][j] = 0;
					Q1.push({ i,j });
				} else if (board[i][j] == '@') {
					playerMoveT[i][j] = 0;
					Q2.push({ i,j });
				}
			}
		}		

		// 2.로직
		// 상근이가 처음부터 가장자리에 있는 경우
		pair<int, int> start = Q2.front();
		if (start.first == 0 || start.first == h - 1 || start.second == 0 || start.second == w - 1) {
			cout << 1 << '\n';
			continue;
		}

		// 지도 전체에 불이 붙는 시간 
		while (!Q1.empty()) {
			pair<int, int> cur = Q1.front();
			Q1.pop();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.first + dx[dir];
				int ny = cur.second + dy[dir];
				if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
				if (board[nx][ny] == '#' || fireMoveT[nx][ny] >= 0) continue;
				fireMoveT[nx][ny] = fireMoveT[cur.first][cur.second] + 1;
				Q1.push({ nx, ny });
			}
		}

		// 상근이의 이동시간
		bool notMove = false;
		while ( (!Q2.empty()) && (!notMove) ) {
			pair<int, int> cur = Q2.front();
			Q2.pop();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.first + dx[dir];
				int ny = cur.second + dy[dir];

				if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
				if (board[nx][ny] == '#') continue;
				if (playerMoveT[nx][ny] >= 0) continue;
				// 상근이의 이동시간이 불의 이동시간보다 무조건 작아야지 상근이가 이동이 가능 (이동시간이 동일하다면 동시에 접근하는 경우이기 때문에 이동 X)
				// 단, 불의 초기값을 -1로 세팅해놓았기 때문에 불이 없는 경우 -1보다 작은 값이 나오지 않기 때문에 이동이 불가능하므로 -1은 제외한다
				if (fireMoveT[nx][ny] != -1 && playerMoveT[cur.first][cur.second] + 1 >= fireMoveT[nx][ny]) continue;

				// 가장자리에 있는 경우 다음 for문에서 탈출하니까 여기서 이동시간 체크
				// **상근이가 처음부터 가장자리에 있는 경우는 이 식이 실행이 안됨**
				if (nx == 0 || nx == h-1 || ny == 0 || ny == w-1) {
					cout << playerMoveT[cur.first][cur.second] + 2 << "\n";
					notMove = true;
					break;
				}
				
				playerMoveT[nx][ny] = playerMoveT[cur.first][cur.second] + 1;
				Q2.push({ nx, ny });
			}
		}

		if (notMove == false) cout << "IMPOSSIBLE" << "\n";
	}


	return 0;
}

 

풀이방법은 생각해냈지만 구현단계에서 많은 어려움을 겪음

생각하지도 못한 반례들에서 실패함 난이도는.. 지금까지 풀었던 BFS중에 가장 어려웠음

 

 

재풀이 코드

#include<iostream>	
#include<queue>
using namespace std;

char board[1001][1001];
int fireDis[1001][1001];
int playerDis[1001][1001];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int w, h;


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while (t--) {
		cin >> w >> h;
		queue<pair<int, int>> Q1; // 불 이동 BFS
		queue<pair<int, int>> Q2; // 상근 이동 BFS
		for (int i = 0; i < h; i++) {
			string str;
			cin >> str;
			for (int j = 0; j < w; j++) {
				board[i][j] = str[j];
				// 불 또는 상근이가 있는 첫 위치를 0초로 시작하기 때문에 방문하지 않은 칸은 -1로 설정
				fireDis[i][j] = -1;
				playerDis[i][j] = -1;
				if (str[j] == '*') {
					fireDis[i][j] = 0;
					Q1.push({ i,j });
				}
				else if (str[j] == '@') {
					playerDis[i][j] = 0;
					Q2.push({ i,j });
				}
			}
		}

		// 1.불이 붙는 모든 시간을 계산
		while (!Q1.empty()) {
			pair<int, int> cur = Q1.front(); Q1.pop();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.first + dx[dir];
				int ny = cur.second + dy[dir];
				if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
				if (board[nx][ny] == '#' || fireDis[nx][ny] >= 0)continue;
				fireDis[nx][ny] = fireDis[cur.first][cur.second] + 1;
				Q1.push({ nx, ny });
			}
		}

		// 2.상근이의 이동시간 계산
		bool exitCheck = false;
		while (!Q2.empty() && (!exitCheck)) {
			pair<int, int> cur = Q2.front(); Q2.pop();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.first + dx[dir];
				int ny = cur.second + dy[dir];

				// 가장자리에서 한칸 더 이동하는 경우 board의 범위를 빠져나가기 때문에 탈출로 판단
				if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
					cout << playerDis[cur.first][cur.second] + 1 << '\n';
					exitCheck = true;
					break;
				}
				
				if (fireDis[nx][ny] != -1 && playerDis[cur.first][cur.second] + 1 >= fireDis[nx][ny]) continue;
				if (board[nx][ny] == '#' || playerDis[nx][ny] >= 0) continue;
				playerDis[nx][ny] = playerDis[cur.first][cur.second] + 1;
				
				Q2.push({ nx, ny });
			}
		}

		if (!exitCheck) cout << "IMPOSSIBLE" << '\n';
	}		
		
	return 0;
}

 

2달 전에 풀었던 문제지만, 해설지를 참고해서 품

어느 정도 구현방법은 맞았지만 디테일한 예외부분에 대해서 생각하지 못함