문제 해석
(N, M) 크기의 성에서 용사가 공주님을 구하러 가는 문제이다.
(1, 1)에서 출발한 용사가 (N, M)에 있는 공주님을 구하는 데 걸리는 최단 시간을 출력해야 하는데, 이 때 두 가지 케이스로 나눌 수 있다.
- 검을 구하지 않는 경우의 최단 경로
- 검을 구한 경우의 최단 경로
예제의 그림에서 볼 수 있듯,
검을 구한 뒤로부턴 벽을 부술 수 있으므로, 벽을 무시하게 된다.
검을 구하지 않은 경우엔 벽을 돌아가야 하므로 16,
검을 구한 경우엔 검을 찾고 그 다음부턴 벽을 무시하므로 10이 걸리게 된다.
시행착오
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
cin >> map[i][j]; // 성 구조 입력받음
if (map[i][j] == 2) { // 그람이 있는 경우
sword = true;
}
}
}우선 처음에는 입력에서부터 성 안에 검이 있는지를 확인한 뒤,
검이 있는 경우와 그렇지 않은 경우로 나뉘어 각각의 BFS를 시도했다.
if (sword) { // 검이 있는 성
// [일반 BFS -> 공주까지의 최단거리] vs
// [검까지의 최단거리 + 검에서 공주까지 벽을 무시한 거리]
}
else { // 검이 없는 성
// [일반 BFS -> 공주까지의 최단거리]
}검이 있는 경우에는 그냥 용사에서 공주까지의 최단 거리와, 검까지의 최단 거리 + 검에서부터 공주까지의 벽을 무시한 최단 거리를 비교하여 더 작은 값을 출력하게 하였다.
그러나 이 방법은 코드가 너무 길어져 가독성이 떨어져 문제를 풀면서 뇌정지가 오는 바람에 포기하게 되었다.
시행착오 2트
성 안에 검이 있든 없든, 하나의 BFS 로직 안에서 굴러가도록 수정하였다.
queue<pair<pair<pair<int, int>, int>, bool>> q;
q.push({ { {1, 1}, 0}, false }); // (1, 1)에서 t=0, 검 X
bool visited[101][101][2] = { false }; // [x][y][검을 들고있는지 여부]
visited[1][1][0] = true; // (1, 1)을 검 X 방문다음과 같이, 큐에는 현재 좌표, 걸린 시간, 검을 들고있는지의 여부.
visited 배열에는 현재 좌표, 검을 들고있는지의 여부, 방문 여부를 정의한다.
queue<pair<pair<pair<int, int>, int>, bool>> q;
queue<pair<tuple<int, int, int>, bool>> q;그러나 이 부분 에서 빌드 에러가 발생했고, tuple로 바꿔주어도 동일한 에러가 발생하였다.
이 상황에서 C2397, C2398 에러는 위의 식과 같이 복잡한 중첩된 형식을 사용할 경우, 컴파일러가 해당 식을 잘못 해석하는 경우 생긴다고 한다.
그래서 어떻게 했는데
그래서 구조체를 선언하여 큐의 형식을 손봐주었다.
struct P { int x, y, t, sword; };
queue<P> q;
q.push({ 1, 1, 0, false }); // (1, 1)에서 t=0, 검 X이랬더니 바로 빌드 에러가 없어졌당. 🙃
어쨌거나 BFS 이전까지의 코드는 아래와 같다.
#include <iostream>
#include <queue>
using namespace std;
int N, M, T;
int map[101][101];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
int main() {
cin >> N >> M >> T;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
cin >> map[i][j];
}
}
struct P { int x, y, t, sword; };
queue<P> q;
q.push({ 1, 1, 0, false }); // (1, 1)에서 t=0, 검 X
bool visited[101][101][2] = { false }; // [x][y][검을 들고있는지 여부]
visited[1][1][0] = true; // (1, 1)을 검 X 방문N, M, T와 map[][] 배열을 전역변수로 설정하고, BFS에서 이동하기 위한 dx[], dy[]를 정의했다.
main 함수 안에선 그 값과 성의 구조를 입력받고 출발점의 상태를 큐와 visited 배열에 저장했다.
while (!q.empty()) {
int currX = q.front().x;
int currY = q.front().y;
int time = q.front().t;
bool sword = q.front().sword;
q.pop();
if (time > T) continue; // T보다 오래 걸림
if (currX == N && currY == M) { // 공주에게 도착
cout << time << "\n";
return 0;
}
for (int i = 0; i < 4; i++)
{
int nextX = currX + dx[i];
int nextY = currY + dy[i];
int nextT = time + 1;
int nextSword = sword;최소 경로를 찾는데 BFS를 이용하기 위해, 큐가 빌 때까지 while 문을 수행한다.
현재 루프의 X, Y좌표, 걸린 시간, 검을 들고있는 지 여부를 각각의 변수에 저장하고, 큐를 pop 한다.
이후 while문의 탈출 조건을 정의해 주는데,
걸린 시간 time이 T보다 길어지면 continue 하여 남은 루프를 그냥 지나쳐주고,
(N, M)에 도착하여 공주님을 구했다면 time을 출력하고 main 함수를 종료한다.
이동 벡터에서는 그 다음칸의 X, Y, time, sword를 정의한다.
// 범위 벗어남 & 방문 확인
if (nextX >= 1 && nextX <= N && nextY >= 1 && nextY <= M
&& !visited[nextX][nextY][nextSword] && map[nextX][nextY] == 0) {
visited[nextX][nextY][nextSword] = true;
q.push({ nextX, nextY, nextT, nextSword });
}
// 검이 있는데 벽을 만남 & 방문 확인
else if (map[nextX][nextY] == 1 && sword
&& !visited[nextX][nextY][nextSword]) {
visited[nextX][nextY][nextSword] = true;
q.push({ nextX, nextY, nextT, nextSword });
}
// 검이 없는데 벽을 만남 & 방문 확인
else if (map[nextX][nextY] == 1 && !sword
&& !visited[nextX][nextY][nextSword]) {
continue;
}
// 검 줍줍 & 방문 확인
else if (map[nextX][nextY] == 2 && !sword
&& !visited[nextX][nextY][nextSword]) {
nextSword = true;
visited[nextX][nextY][nextSword] = true;
q.push({ nextX, nextY, nextT, nextSword });
}
}
}그리고 nextX, nextY에 도착했을 때 각각의 경우에 따라 다른 작업을 수행하는데,
각 칸의 방문할때의 모든 경우의 수를 나누다 보니 너무 식이 길어졌다.
따라서 이 부분을 다듬어 아래에 다시 서술했다.
cout << "Fail";
return 0;
}마지막으로는 while문에서 continue 되어 빠져나온 경우 Fail을 출력하도록 했다.
더 나은 방법
// 범위를 벗어남
if (nextX < 1 || nextX > N || nextY < 1 || nextY > M) {
continue;
}
// 방문함
if (visited[nextX][nextY][nextSword]) {
continue;
}
// 검이 없는데 벽을 만남
if (map[nextX][nextY] == 1 && !sword) {
continue;
}
// 검 줍줍
if (map[nextX][nextY] == 2 && !sword) {
nextSword = true;
}
// 범위 내, 방문 X, 벽 아닌 칸, 검 있는데 벽
visited[nextX][nextY][nextSword] = true;
q.push({ nextX, nextY, nextT, nextSword });위의 조건문에서, 중복되는 visited 배열의 방문과, 큐의 삽입을 하나로 합쳤다.
큐에 삽입하지 않는 부분만 따로 떼어 continue로 루프를 지나가게 하였고,
검을 주운 경우 sword를 true로 만든 뒤 visited를 방문처리 하고, 큐에 삽입한다.
전체 코드는 다음과 같다.
#include <iostream>
#include <queue>
using namespace std;
int N, M, T;
int map[101][101];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
int main() {
cin >> N >> M >> T;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
cin >> map[i][j];
}
}
struct P { int x, y, t, sword; };
queue<P> q;
q.push({ 1, 1, 0, false }); // (1, 1)에서 t=0, 검 X
bool visited[101][101][2] = { false }; // [x][y][검을 들고있는지 여부]
visited[1][1][0] = true; // (1, 1)을 검 X 방문
while (!q.empty()) {
int currX = q.front().x;
int currY = q.front().y;
int time = q.front().t;
bool sword = q.front().sword;
q.pop();
if (time > T) continue; // T보다 오래 걸림
if (currX == N && currY == M) { // 공주에게 도착
cout << time << "\n";
return 0;
}
for (int i = 0; i < 4; i++)
{
int nextX = currX + dx[i];
int nextY = currY + dy[i];
int nextT = time + 1;
int nextSword = sword;
// 범위를 벗어남
if (nextX < 1 || nextX > N || nextY < 1 || nextY > M) {
continue;
}
// 방문함
if (visited[nextX][nextY][nextSword]) {
continue;
}
// 검이 없는데 벽을 만남
if (map[nextX][nextY] == 1 && !sword) {
continue;
}
// 검 줍줍
if (map[nextX][nextY] == 2 && !sword) {
nextSword = true;
}
// 범위 내, 방문 X, 벽 아닌 칸, 검 있는데 벽
visited[nextX][nextY][nextSword] = true;
q.push({ nextX, nextY, nextT, nextSword });
}
}
cout << "Fail";
return 0;
}
크크루삥뽕
