17836번 공주님을 구해라!

https://www.acmicpc.net/problem/17836

 

 

1. 방문 처리할 때, 그람을 먹었는지와 아직 먹지 않았는지 2가지를 따져야한다. 즉, 3차원 방문 처리

 

2. 제한시간인 T시간을 고려하여 구현한다. 그냥 현재 그 순간의 시간(d)을 활용하여 T와 비교하면 된다. 도착했을 때, 이제 먹으려고 할 때 d vs T

 

 

#include<bits/stdc++.h>

using namespace std;

#define MAX 101

typedef struct{
    int r, c, g, d;
}info;

int N, M, T;
int m[MAX][MAX];
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
bool used[MAX][MAX][2]; // 0 : 그람을 먹지 않았을 경우, 1 : 그람을 먹었을 경우

int bfs()
{
    int ret = INT32_MAX;

    // { 행(y), 열(x), 그람을 먹었는지 여부, 거리 } 
    queue<info> q;
    q.push({ 0, 0, 0, 0 });
    used[0][0][0] = true;

    while (!q.empty())
    {
        int qs = q.size();
        while (qs--)
        {
            int r = q.front().r;
            int c = q.front().c;
            int g = q.front().g;
            int d = q.front().d;

            q.pop();

            if (r == N - 1 && c == M - 1 && d <= T) {
                ret = min(ret, d);
            }

            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];

                if (y < 0 || y >= N || x < 0 || x >= M || used[y][x][g]) {
                    continue;
                }

                // 그람을 먹었을 경우
                if (g == 1 && d < T) {
                    q.push({ y, x, 1, d + 1 });
                    used[y][x][1] = true;
                }
                // 그람을 먹지 않았을 경우
                else {
                    // (y, x)가 그람인 경우
                    if (m[y][x] == 2 && d < T) {
                        q.push({ y, x, 1, d + 1 });
                        used[y][x][1] = true;
                    }
                    // (y, x)가 그람이 아닌 경우 = 빈 칸, (1은 장애물이므로 제외)
                    else if (m[y][x] == 0 && d < T) {
                        q.push({ y, x, 0, d + 1 });
                        used[y][x][0] = true;
                    }
                }
            }
        }
    }

    if (ret == INT32_MAX) {
        return -1;
    }

    return ret;
}

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);

    scanf("%d %d %d", &N, &M, &T);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &m[i][j]);
        }
    }

    int ans = bfs();
    if (ans == -1) {
        printf("Fail\n");
    }
    else {
        printf("%d\n", ans);
    }

    return 0;
}