[Baekjoon] 공주님을 구해라!
👀 문제 설명
용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.
마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 싶은 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸린다. 공주님이 있는 곳에 정확히 T시간만에 도달한 경우에도 구출할 수 있다. 용사는 상하좌우로 이동할 수 있다.
성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.
우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.
입력
첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)
두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.
출력
용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.
만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.
예제 입력 1
6 6 16
0 0 0 0 1 1
0 0 0 0 0 2
1 1 1 0 1 0
0 0 0 0 0 0
0 1 1 1 1 1
0 0 0 0 0 0
예제 출력 1
10
주황색 선을 따라 검을 구하지 않고, 벽을 돌아가면 16시간만에 공주님에게 도착할 수 있다.
반면, 녹색선을 따라 "그람"을 구해, 벽을 부수고 공주님께 가면 10시간만에 도달할 수 있다.
예제 입력 2
3 4 100
0 0 0 0
1 1 1 1
0 0 2 0
예제 출력 2
Fail
✍🏻풀이
큐를 사용해 문제를 풀면 된다.
나는 큐에 저장하는 방식을 { { i, j }, 그람 유무 } 이렇게 해서 그람이 있으면, 벽을 무시하고 BFS를 돌리고, 그람이 없다면 벽을 인지하고 BFS를 돌려 답을 구했다.
하지만 이런 식으로 푸니까 메모리 초과가 났다.. 문제는 그람이 있는데도 하나하나 BFS를 돌려서 그런 거였다..! 그람이 있으면 벽을 다 부수고 무조건 직진할 수 있으니까 BFS를 돌릴 필요 없이 abs(N - nextX) + abs(M - nextY)를 rescueTime[nextX][nextY]에 더해주면 쉽게 풀 수 있다!!
자세한 설명은 코드에 주석으로 달아놨다.
코드
메모리 초과
// 공주님을 구해라! (https://www.acmicpc.net/problem/17836)
#include <iostream>
#include <queue>
#define MAX 101
#define INF 987654321;
using namespace std;
int castle[MAX][MAX];
int rescueTime[MAX][MAX];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
bool getGram = 0;
/**
* 1. 벽(1)인 경우, continue
* 2. 그람(2)인 경우,
*
*/
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
// input
int N, M, T;
cin >> N >> M >> T;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> castle[i][j];
rescueTime[i][j] = INF;
}
}
// solve
queue<pair<pair<int, int>, int> > Q; // {{ i, j }, 그람 유무}로 저장. (i, j)의 위치에 그람이 있는지
Q.push({ { 1, 1 }, 0});
rescueTime[1][1] = 0;
// Q.push({ { 1, 1 }, 0 }); // 출발 지점 (1, 1) 그람은 없음
while (!Q.empty()) {
int curX = Q.front().first.first;
int curY = Q.front().first.second;
bool gram = Q.front().second; // 그람 유무
Q.pop();
if (getGram) {
if (gram == 0)
continue;
else {
for (int dir = 0; dir < 4; dir++) {
int nextX = curX + dx[dir];
int nextY = curY + dy[dir];
if (nextX <= 0 || nextX > N || nextY <= 0 || nextY > M) // 범위를 벗어나면 continue
continue;
if (rescueTime[nextX][nextY] >= rescueTime[curX][curY] + 1) { // 벽을 뚫고 갈 수 있다.
rescueTime[nextX][nextY] = rescueTime[curX][curY] + 1;
Q.push({ { nextX, nextY }, 1 }); // 현재 그람을 갖고 있다고 알려줘야 함
}
}
}
}
if (gram) { // 그람을 갖고 있는 경우
getGram = 1;
for (int dir = 0; dir < 4; dir++) {
int nextX = curX + dx[dir];
int nextY = curY + dy[dir];
if (nextX <= 0 || nextX > N || nextY <= 0 || nextY > M) // 범위를 벗어나면 continue
continue;
if (rescueTime[nextX][nextY] >= rescueTime[curX][curY] + 1) { // 벽을 뚫고 갈 수 있다.
rescueTime[nextX][nextY] = rescueTime[curX][curY] + 1;
Q.push({ { nextX, nextY }, 1 }); // 현재 그람을 갖고 있다고 알려줘야 함
}
}
}
else { // 그람이 없는 경우
for (int dir = 0; dir < 4; dir++) {
int nextX = curX + dx[dir];
int nextY = curY + dy[dir];
if (nextX <= 0 || nextX > N || nextY <= 0 || nextY > M) // 범위를 벗어나면 continue
continue;
if (castle[nextX][nextY] == 1) // 벽(1)인 경우, continue
continue;
if (rescueTime[nextX][nextY] > rescueTime[curX][curY] + 1) {
rescueTime[nextX][nextY] = rescueTime[curX][curY] + 1;
// 가능한 범위
// 1. 그람이 있는 경우
if (castle[nextX][nextY] == 2) {
Q.push({ { nextX, nextY }, 1 });
}
// 2. 그람이 아닌 그냥 길인 경우
else { // castle[nextX][nextY] == 0
Q.push({ { nextX, nextY }, 0 });
}
}
}
}
}
if (rescueTime[N][M] <= T)
cout << rescueTime[N][M] << "\n";
else
cout << "Fail\n";
return 0;
}
정답 - 코드 긴 버전
// 공주님을 구해라! (https://www.acmicpc.net/problem/17836)
#include <iostream>
#include <queue>
#define MAX 101
#define INF 987654321;
using namespace std;
int castle[MAX][MAX];
int rescueTime[MAX][MAX];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
/**
* 1. 벽(1)인 경우, continue
* 2. 그람(2)인 경우,
*
*/
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
// input
int N, M, T;
cin >> N >> M >> T;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> castle[i][j];
rescueTime[i][j] = INF;
}
}
// solve
queue<pair<pair<int, int>, int> > Q; // {{ i, j }, 그람 유무}로 저장. (i, j)의 위치에 그람이 있는지
Q.push({ { 1, 1 }, 0});
rescueTime[1][1] = 0;
while (!Q.empty()) {
int curX = Q.front().first.first;
int curY = Q.front().first.second;
bool gram = Q.front().second; // 그람 유무
Q.pop();
if (gram) { // 그람을 갖고 있는 경우
rescueTime[N][M] = min(rescueTime[N][M], rescueTime[curX][curY] + abs(N - curX) + abs(M - curY));
}
else { // 그람이 없는 경우
for (int dir = 0; dir < 4; dir++) {
int nextX = curX + dx[dir];
int nextY = curY + dy[dir];
if (nextX <= 0 || nextX > N || nextY <= 0 || nextY > M) // 범위를 벗어나면 continue
continue;
if (castle[nextX][nextY] == 1) // 벽(1)인 경우, continue
continue;
if (rescueTime[nextX][nextY] > rescueTime[curX][curY] + 1) {
rescueTime[nextX][nextY] = rescueTime[curX][curY] + 1;
// 가능한 범위
// 1. 그람이 있는 경우
if (castle[nextX][nextY] == 2) {
Q.push({ { nextX, nextY }, 1 });
}
// 2. 그람이 아닌 그냥 길인 경우
else { // castle[nextX][nextY] == 0
Q.push({ { nextX, nextY }, 0 });
}
}
}
}
}
if (rescueTime[N][M] <= T)
cout << rescueTime[N][M] << "\n";
else
cout << "Fail\n";
return 0;
}
정답 - 코드 줄인 버전
// 공주님을 구해라! (https://www.acmicpc.net/problem/17836)
#include <iostream>
#include <queue>
#define MAX 101
#define INF 987654321;
using namespace std;
int castle[MAX][MAX];
int rescueTime[MAX][MAX];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
/**
* 1. 벽(1)인 경우, continue
* 2. 그람(2)인 경우, min(rescueTime[N][M], rescueTime[nextX][nextY] + abs(N - nextX) + abs(M - nextY))를 rescueTime[N][M]에 대입
* -> 그람을 획득하면, 벽을 부수고 앞으로 계속해서 나아갈 수 있으므로
*
*/
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
// input
int N, M, T;
cin >> N >> M >> T;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> castle[i][j];
rescueTime[i][j] = INF;
}
}
// solve
queue< pair<int, int> > Q;
Q.push({ 1, 1 });
rescueTime[1][1] = 0;
while (!Q.empty()) {
int curX = Q.front().first;
int curY = Q.front().second;
Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nextX = curX + dx[dir];
int nextY = curY + dy[dir];
if (nextX <= 0 || nextX > N || nextY <= 0 || nextY > M) // 범위를 벗어나면 continue
continue;
if (castle[nextX][nextY] == 1) // 벽(1)인 경우, continue
continue;
if (rescueTime[nextX][nextY] > rescueTime[curX][curY] + 1) {
rescueTime[nextX][nextY] = rescueTime[curX][curY] + 1;
// 가능한 범위
// 1. 그람이 있는 경우
if (castle[nextX][nextY] == 2) {
// 그람을 획득하면 벽을 부수고 계속 이동할 수 있으므로, 가장 짧은 거리는 rescueTime[nextX][nextY] + abs(N - nextX) + abs(M - nextY)이다.
rescueTime[N][M] = min(rescueTime[N][M], rescueTime[nextX][nextY] + abs(N - nextX) + abs(M - nextY));
}
// 2. 그람이 아닌 그냥 길인 경우
else { // castle[nextX][nextY] == 0
Q.push({ nextX, nextY });
}
}
}
}
// if (rescueTime[N][M] <= T)
// cout << rescueTime[N][M] << "\n";
// else
// cout << "Fail\n";
cout << ((rescueTime[N][M] <= T) ? to_string(rescueTime[N][M]) : "Fail") << "\n"; // 위의 4줄을 이렇게 줄일 수 있다. (단, to_string으로 변환해야 함)
return 0;
}