조건 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을 주은 지점을 끝으로 좌표 계산하면 된다....