[백준 17836] 공주님을 구해라!

문제 출처: https://www.acmicpc.net/problem/17836

풀이

여러가지 bfs문제를 풀면서 특정 조건이 있을 때 3차원배열을 이용할 수 있음을 배웠습니다.

예를들어 

1. 길을 탐색할 때 벽을 뚫고가거나 벽을 뚫지않고 갈때 도착점에 도달시 최단거리

2. 검을 먹고 도착하거나 검을 먹지않고 도착할 때 최단거리

같은 경우, 기존의 2차원visited배열을 3차원으로 visited[크기][크기][2]로 선언해서 인덱스가 0이고 값이0일 때 벽을 뚫지않고/검을 먹지않고 그 좌표에 도착하지않았음을 의미하고 인덱스가 1이고 값이 1일때 벽을 뚫고/검을 먹고 도착하였다로 해석 할 수 있습니다. 되게 유용한 것 같습니다.

문제에대해 풀이순서대로 작성해보았습니다.

1. visited배열 선언시 3차원으로 선언하여 검을먹고/먹지않고를 표현할 수 있게한다. 

2. y좌표,x좌표, 걸린시간, 검을획득했는지여부를 구조체로 저장하여 큐에담아서 bfs를 돌린다.

3. 검을 만나면 get을 1로 바꿔주고, 도착점에 도착하면 탈출하여 값 출력하기

일반적인 bfs는 다돌려놓고 도착점의 좌표의 visited배열값을 출력하지만 이 문제는 검을 먹고도착/먹지않고 도착 2가지경우가 있으므로 도착했을 때, 큐에 아직 길을 가고있는 좌표들이있던말던 상관없이 도착하기만 하면 그게 곧 최단거리이므로 탈출하여 값 출력한다. 

그렇기 때문에 문제예제처럼 16s가 걸리던 10s가 걸리던 더 짧은 시간을 비교할필요가없음

4. visited배열에 진행시간을 수정해나갈 때 주의하기

일반적인 bfs는 visted[ny][nx]=visited[y][x]+1하여 최단거리를 찾지만, 이 문제는 검을먹고/먹지않고 가는 좌표가 검획득여부에따라 다름

무슨말이냐면, 같은좌표를 가도, 3차원배열이기 때문에 먹지않고 도착하는좌표와 먹고 도착하는좌표의 값은 서로 다름 

따라서 문제예제를보면, 위처럼 코드작성 시 검을 먹은위치는 6이아닌 0이된다. 

검 먹을 때 get이 1이되므로 검을 먹은좌표가 "검을먹은상태에서 검을먹기직전까지온 시간+1로 해석된다.

검의 좌표는 검을 먹지않은 상태에서 검을 먹기직전까지 온 시간 +1이 되어야한다.

따라서 visited[ny][nx][get]=cnt+1로 작성해야한다.

5. 벽 뚫고 가는것 표현하기

굳이 벽을뚫고가는 모션을 표현할 필요없고, 검을 먹은 뒤부터는 모든 좌표를 갈 수 있으므로 다음좌표를 방문했는지만 확인하면된다.

6. 정답 출력시 ans범위 조심하기

ans<=t인지만 확인하면 ans=0일 때 Fail 대신 0이 출력될수 있으므로 , ans>0 or ans>=1의 조건을 붙여준다.

코드

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct info
{
    int y, x, cnt, get;
};
int n, m, t, castle[100][100], visited[100][100][2], ans;
int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
void bfs(int y,int x,int cnt,int get);
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin >> n >> m >> t;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> castle[i][j];
 
    //y좌표,x좌표,걸린시간,검획득여부
    bfs(0, 0, 0,0);
    if (ans>=1&&ans <= t)cout << ans << '\n';
    else cout << "Fail" << '\n';
}
void bfs(int y,int x,int cnt,int get)
{
    queue<info>q;
    q.push({ y,x,cnt,get });
    visited[y][x][get] = 1;
    while (!q.empty())
    {
        y = q.front().y;
        x = q.front().x;
        get = q.front().get;
        cnt = q.front().cnt;
        
        q.pop();
        //검을먹으면 get을 1로바꿔줌
        if (castle[y][x] == 2)get = 1;
        //도착하면 탈출하기
        //탈출해야 최단거리를 알수있음
        if (y == n - 1 && x == m - 1)
        {
            ans = cnt;
            return;
        }
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            //검 얻었을 때
            if (get == 1)
            {
                if (ny >= 0 && nx >= 0 && ny < n && nx < m)
                {
                    if (visited[ny][nx][get] == 0)
                    {
                        visited[ny][nx][get] = cnt + 1;
                        q.push({ ny,nx,visited[ny][nx][get],get });
                    }
                }
            }
            //검 못먹었을 때
            else
            {
                if (ny >= 0 && nx >= 0 && ny < n && nx < m)
                {
                    if (visited[ny][nx][get] == 0 && castle[ny][nx] != 1)
                    {
                        visited[ny][nx][get] = cnt + 1;
                        q.push({ ny,nx,visited[ny][nx][get],get });
                    }
                }
            }
        }
    }
}

결과