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

[문제보기]

 

[해결과정]

 1. 맵 저장 배열(2차원), 방문 체크 배열(3차원), 구조체(y좌표, x좌표, 방문시간, 검획득여부) 큐 생성

 2. (0,0)부터 BFS 탐색 시작

  2-1. 만약 방문 좌표가 검이 있는 곳이면, 다음 방문확인은 check[y][x][1] 에서 확인.

  2-2. 아직 검을 찾지 못했다면, 다음 방문확인은 check[y][x][0] 에서 확인. 

 3. 공주님을 찾으면 시간 값을 저장하고 return;

 

<사진> 좌측 : 검 안먹었을 때 (check[y][x][0]) , 우측 : 검 먹었을 때 (check[y][x][1])

 

위 사진과 같이 검을 안먹었을 때는 check[y][x][0]에서 BFS탐색을 계속하고,

만약 검을 먹었을 경우는 check[y][x][1]에서 검 먹기전 시간을 이어 탐색을 한다. 이때, 검을 먹었을 경우에는 벽을 모두 부술 수 있으니, map 체크를 하지 않아도 된다. (우측 사진처럼 벽이 모두 없다고 판단)

 

[소스코드]

#include<iostream>
#include<queue>
using namespace std;
 
const int MAX = 103;
int n, m, t;
int arr[MAX][MAX];
int check[MAX][MAX][2];
 
int flag = 0;
int ans = 0;
 
struct coor {
    int y;
    int x;
    int cnt;
    int g;
};
queue <coor> q;
 
//inside check
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < m;
}
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void bfs() {
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        int g = q.front().g;
        q.pop();
 
        if (arr[y][x] == 2) g = 1;
        if (y == n - 1 && x == m - 1) {
            ans = cnt - 1;
            return;
        }
 
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (g == 1) {
                if (inside(ny, nx) && check[ny][nx][g] == 0) {
                    check[ny][nx][g] = cnt + 1;
                    q.push({ ny,nx,cnt + 1,g });
                }
            }
            else {
                if (inside(ny, nx) && check[ny][nx][0] == 0 && arr[ny][nx] != 1) {
                    check[ny][nx][0] = cnt + 1;
                    q.push({ ny,nx,cnt + 1,g});
                }
            }
            
        }
    }
}
 
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 >> arr[i][j];
        }
    }
 
    check[0][0][0] = 1;
    q.push({ 0,0,1,0 });
 
    bfs();
 
    if (ans > 0 && ans <= t) cout << ans;
    else cout << "Fail";
 
 
 
    return 0;
}

 

 

 

[해결 과정 중 실수한 부분]

 처음 문제를 보고 10분 만에 소스 코드를 완성했다. 유사한 문제는 벽 부수고 이동하기랑 굉장히 비슷했다. 근데, 검을 획득했어도... 검을 획득 안한 부분도 계속 진행해줘야 한다는 멍청한 생각을 계속 하고 있었다...

그래서 "왜 안되지........" 고민 하다 정답률을 왕창 떨어뜨렸다 ㅎㅎ..

 

[관련 문제 혹은 비슷한 문제]

백준 벽부수고 이동하기 문제집