백준 4179번 불! C++

리뷰

어차피 불에 닿으면 타죽으니 범위를 지정해 주지 않아 OutOfBounds 에러가 떴다. 다시 생각해 보니 범위는 꼭 지정해 줘야 했다.

기존의 BFS문제와 같지만 지훈이와 불의 입장에서 모두 생각해 주어야 하는 문제

 

문제 풀이

1. r, c와 미로 정보를 받아준다. 나는 1차 문자열 배열로 미로를 받아와 주었다.
2. 좌표 및 지훈이 여부, 시간 등의 정보를 pos 구조체로 정의해 주었다.
3. 큐대신 덱으로 받아와 만약 지훈이의 위치라면 push_front를, 불의 정보랑 push_back으로 정보를 받아와 줬다. 이때 j변수를 불이라면 0, 지훈이라면 1로 초기화 해주고, t변수를 지훈이라면 1, 불이라면 0으로 초기화 해줬다.
4. while 루프를 시작하고 pop 후 현재 위치가 가장자리면서 지훈이라면 time을 리턴해 주는 기저조건을 실행한다.
5. 종료조건에 해당하지 않는다면 4방향을 탐색해 준다. 이때도 지훈이와 불의 정보를 각각 실행해 줘야 한다.
6. 현재 지훈이면서 다음 위치가 미로의 범위를 벗어나지 않고 벽이 아니고 방문하지 않은 곳이라면 다음 위치에 방문 표시를  1로 해주고 시간을 1 늘린 후 큐에 추가해 준다.
7. 현재 지훈이가 아니면서 다음 위치가 미로의 범위를 벗어나지 않고 벽이 아니고 방문하지 않았거나 지훈이가 다녀간 위치라면 방문 표시를 2로 해주고 시간은 상관없으니 0인 상태로 큐에 추가해 준다.
8. 만약 while 루프 내 지훈이가 미로를 탈출했다면 time을 리턴, 아니라면 -1을 리턴해 준다.
9. bfs의 리턴값을 받고 -1이라면 IMPOSSIBLE을, -1이 아니라면 ans에 저장된 값을 출력하면 된다.

 

참고 사항

가장자리에 닿으면 자동으로 종료되기에 미로의 범위를 벗어나는지를 체크하지 않아도 된다고 생각했다.

지훈이의 경우에는 그래도 되지만 불의 경우에는 return되지 않으므로 Out of bounds 에러가 노출되기에 if문에서 꼭 조건을 설정해 주어야 한다. (벽이나 방문 여부를 체크하기 전에 넣어줘야 한다.)

 

정답 코드

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

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

int r, c;
vector<string> lst;

struct pos {
	int x, y, j, t;
};

int bfs() {
	deque<pos> q;
	vector<vector<int>> v(r, vector<int>(c, 0));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (lst[i][j] == 'J') {
				q.push_front({ i, j, 1, 1 });
				v[i][j] = 1;
			}
			if (lst[i][j] == 'F') {
				q.push_back({ i, j, 0, 0 });
				v[i][j] = 2;
			}
		}
	}

	while (!q.empty()) {
		pos now = q.front();
		q.pop_front();
		int cx = now.x, cy = now.y, jf = now.j, time = now.t;
		if (cx == 0 || cx == r - 1 || cy == 0 || cy == c - 1) {
			if (v[cx][cy] == 1) return time;
		}
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (jf && 0 <= nx && nx < r && 0 <= ny && ny < c && lst[nx][ny] != '#' && !v[nx][ny]) {
				v[nx][ny] = 1;
				q.push_back({ nx, ny, jf, time + 1 });
			}
			if (!jf && 0 <= nx && nx < r && 0 <= ny && ny < c && lst[nx][ny] != '#' &&v[nx][ny] <= 1) {
				v[nx][ny] = 2;
				q.push_back({ nx, ny, jf, 0 });
			}
		}
	}
	return -1;
}

int main() {
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		string s;
		cin >> s;
		lst.push_back(s);
	}
	int ans = bfs();
	if (ans == -1) cout << "IMPOSSIBLE";
	else cout << ans;
}