백준 17836 공주님을 구해라! (C++)

17836번: 공주님을 구해라!

bfs를 이용한 문제이다. 시작 지점을 0,0, 시간 그리고 그람 유무를 가지는 큐를 만들어주었다. 그리고 bfs를 돌며 그람을 가질 경우 true로 바꿔주고 공주를 만날 경우의 시간을 저장해주고 T와 비교하여 답을 출력해주었다. 지나온 길을 확인하는 check를 보면 좌표와 bool값을 저장하는데 그람을 만났을때 다시 지나온 길을 돌아가는게 빠를 경우도 존재할 수 있기에 따로 저장해주었다.
쉽게 풀 수 있었던 문제였다. 확실히 bfs 문제를 많이 풀어봐서인지 빠르게 풀 수 있었다.

#include <iostream>
#include <queue>

using namespace std;

int N, M, T;
int A[100][100];
bool check[100][100][2];
int gramx, gramy;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int result = 10001;

void bfs() {
	queue<pair<pair<int, int>, pair<int, bool>>> q;

	q.push({ {0,0},{0,false} });

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int time = q.front().second.first;
		bool gram = q.front().second.second;

		if (y == N - 1 && x == M - 1) {
			result = time;
			break;
		}

		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			int ng = gram;

			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (!gram && A[ny][nx] == 1) continue;
			if (check[ny][nx][gram]) continue;

			if (A[ny][nx] == 2) ng = true;

			check[ny][nx][gram] = true;
			q.push({ {ny,nx},{time + 1, ng} });
		}
	}
}

void solution() {
	bfs();

	if (result > T) cout << "Fail";
	else cout << result;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M >> T;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> A[i][j];
		}
	}

	solution();
	
	return 0;
}