백준 17836번 공주님을 구해라! 문제풀이(C++)

백준 17836번 공주님을 구해라!

아이디어

조건

1. 시작 지점은 (1,1), 종료지점은 (n, m), 제한 시간은 T
2. 벽이 존재하고 벽은 지나갈 수 없음
3. 전설의 명검 그람을 주우면 벽을 무한대로 부수고 이동 가능

조건에 맞게 구상

조건 1

격자는 2차원 배열로 n, m을 입력 받으면 vector로 생성해야겠다

int castle_row, castle_col, cursing_time; // n, m, t
cin >> castle_row >> castle_col >> cursing_time;
vector<vector<int>>castle(castle_row, vector<int>(castle_col));
for (vector<int>& row : castle)
{
	for (int& element : row)
	{
		cin >> element; // 입력
	}
}

제한시간이 존재하니까 이동 횟수를 제한시간과 비교하자

// 이동 횟수 : move_count
move_count > cursing_time ? 987654321 : move_count

조건 2

벽이 존재하니까 이동 시간 체크할때 조건식이

// next_row, next_col 이동할 위치 / visited 이동했던 곳인지 판단 / castle 벽인지 판단
if (next_row < 0 || next_row >= castle_row || next_col < 0 || next_col >= castle_col || visited[next_row][next_col] || castle[next_row][next_col] == 1) {
	continue;
}

이렇게 되겠네

조건 3

명검을 주운 후로 조건이 바뀌네
그러면 명검까지의 거리 + 명검으로부터 공주까지의 거리를 구해보자

if (castle[next_row][next_col] == 2)
{
// time_to_next_move == 명검까지의 거리 / save_princess == 명검으로부터 공주까지 거리
	time_to_next_move + save_princess(castle, next_row, next_col, castle_row, castle_col, cursing_time, true);
}

추가 조건

명검을 주운후 이동한것과 명검을 줍지 않고 이동한것을 비교해보자!!

조건에 맞게 코드를 순서대로 작성하고 조합을 한다!!!!!

정답 코드

#include<bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
// 이동 방향
constexpr int way_row[] = { 0,1,0,-1 };
constexpr int way_col[] = { 1,0,-1,0 };
struct warrior
{
	// 열, 행, 이동 횟수
	int row;
	int col;
	int time_take_to_move;
};
// 순서대로 / 격자크기, 시작행, 시작 열, 성벽의 행 크기, 성벽의 열 크기, 저주걸리는 시간, gram 을 주운 상태 gram
int save_princess(const vector<vector<int>>& castle, const int start_row, const int start_col, const int castle_row, const int castle_col, const int cursing_time, const bool gram = false)
{
// 방문 상태 visited
	vector<vector<bool>> visited(castle_row, vector<bool>(castle_col));
	// 용사의 상태를 담으 queue
    queue<warrior> warrior_move;
    // initailize
	warrior_move.push({ start_row,start_col,0 });
	visited[start_row][start_col] = true;
    // gram의 유무에 따라 달라지므로 비교하기 위한 move_count
	int move_count = 987654321;
	while (!warrior_move.empty())
	{
		const warrior current_state = warrior_move.front();
		warrior_move.pop();
		const int time_to_next_move = current_state.time_take_to_move + 1;
        // 저주가 먼저면 queue값들 무시
		if (time_to_next_move > cursing_time)
		{
			continue;
		}
        // 4방향으로 이동
		for (int i = 0; i < 4; i++)
		{
			const int next_row = current_state.row + way_row[i];
			const int next_col = current_state.col + way_col[i];
			if (next_row < 0 || next_row >= castle_row || next_col < 0 || next_col >= castle_col || visited[next_row][next_col]) {
				continue;
			}
            // gram을 줍기 전인지 판별하기 위한 if문
			if (!gram && castle[next_row][next_col] == 1)
			{
				continue;
			}
            // gram을 주우면 gram위치 기준으로 다시 bfs
			if (castle[next_row][next_col] == 2)
			{
				move_count = min(move_count, time_to_next_move + save_princess(castle, next_row, next_col, castle_row, castle_col, cursing_time, true));
			}
            // 공주 위치 까지 가면...
			if (next_row == castle_row - 1 && next_col == castle_col - 1)
			{
				move_count = min(move_count, time_to_next_move);
			}
			warrior_move.push({ next_row , next_col, time_to_next_move });
			visited[next_row][next_col] = true;
		}
	}
	// 총 이동 시간이 저주시간보다 길면 초기값 return
	return move_count > cursing_time ? 987654321 : move_count;
}
int main()
{
	FAST_IO;
    // 성벽 행, 열, 저주 시간
	int castle_row, castle_col, cursing_time;
	cin >> castle_row >> castle_col >> cursing_time;
    // 성벽 
	vector<vector<int>>castle(castle_row, vector<int>(castle_col));
	for (vector<int>& row : castle)
	{
		for (int& element : row)
		{
        // 입력
			cin >> element;
		}
	}
	
	const int answer = save_princess(castle, 0, 0, castle_row, castle_col, cursing_time);
    // 공주를 구해내지 못하면...
	if (answer == 987654321)
	{
		cout << "Fail\n";
	}
    // 구했을 때
	else
	{
		cout << answer << '\n';
	}
	return 0;
}

바보같이 gram을 주운 지점을 기준으로 다시 bfs를 돌렸는데 생각해보니 gram을 주은 지점을 끝으로 좌표 계산하면 된다....