C++ / 프로그래머스 / 2회 모의고사 - 보물 지도

문제

 

https://school.programmers.co.kr/learn/courses/15009/lessons/121690

프로그래머스

 

 

문제풀이

 

3차원 벡터 vector[y][x][신발 사용 여부]와 벽을 나타내기 위한 2차원 벡터를 선언하여 풀었다.

맨 왼쪽 아래칸(시작칸)이 (1, 1) 좌표이며 (x=n, y=m)인 도착지점을 가는데 필요한 최소 시간을 구하는 문제이다.

BFS로 문제를 풀었고, queue에는 Coord라는 구조체를 선언하여 입력해 주었다.

y좌표, x좌표와 해당 지점을 갔을 때 신발을 사용했는지 여부를 알려주는 bool형 used_shoes, 총 세 가지 변수로 이루어진 구조체이다.

 

다른 2차원 BFS문제랑 다른 점은 신발 사용 여부이다.

따라서 다음칸이 벽일 때, 여러 가지를 고려해야 한다.

벽다음에 또 벽이 있는지, 신발을 사용해서 현재 지점에 있는지, 벽다음에 좌표를 벗어나는지 등등..

 

먼저 다음 칸이 벽인지를 판단해 주었고, 벽이 아닐 경우는 이동하면 최소 시간으로 가는지를 판별했다.

벽일 경우는 신발을 사용할 수 있는지를 판단한다.

사용할 수 있는 경우 또 다음칸이 벽인지, 벽을 넘는 것이 최소 시간인지를 판별한다.

 

반복문이 종료되면 [m][n][0] (신발을 사용하지 않고 간 최소 시간) - 1 (벽을 만나지 않은 상태로 두칸 이동하는 경우),

[m][n][1] (신발을 사용하여 간 최소 시간) 중 최솟값을 return 하면 된다.

만약 둘 다 갈 수 없다면 -1을 return 하면 된다.

 

코드

#include <string>
#include <vector>
#include <queue>
#define INF 1e7
using namespace std;

int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,-1,1 };

struct Coord {
    int y;
    int x;
    bool used_shoes;
};

int solution(int n, int m, vector<vector<int>> hole) {
    int answer = 0;
    vector<vector<vector<int>>>dist(m + 1, vector<vector<int>>(n + 1, vector<int>(2, INF)));
    vector<vector<bool>>map(m + 1, vector<bool>(n + 1, false));
    queue<Coord>q;

    for (int idx = 0; idx < hole.size(); ++idx) {
        int y = hole[idx][1];
        int x = hole[idx][0];
        map[y][x] = true; // 벽 감지
    }

    Coord coord;
    coord.y = 1, coord.x = 1, coord.used_shoes = false;
    q.push(coord);
    dist[1][1][0] = 0;
    dist[1][1][1] = 0;

    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        bool used_shoes = q.front().used_shoes;
        q.pop();

        for (int idx = 0; idx < 4; ++idx) {
            int next_y = y + dy[idx];
            int next_x = x + dx[idx];
            if (next_y < 1 || next_y > m || next_x < 1 || next_x > n) continue;
            if (dist[next_y][next_x][used_shoes] != INF) continue;
            if (map[next_y][next_x] == false) {
                if (dist[y][x][used_shoes] + 1 < dist[next_y][next_x][used_shoes]) {
                    dist[next_y][next_x][used_shoes] = dist[y][x][used_shoes] + 1;
                    coord.y = next_y, coord.x = next_x, coord.used_shoes = used_shoes;
                    q.push(coord);
                }
            }
            else if (map[next_y][next_x] == true) {
                if (used_shoes == true) continue;
                else if (used_shoes == false) {
                    int jump_y = next_y + dy[idx];
                    int jump_x = next_x + dx[idx];
                    if (jump_y < 1 || jump_y > m || jump_x < 1 || jump_x > n) continue;
                    if (map[jump_y][jump_x] == true) continue;
                    if (dist[jump_y][jump_x][true] != INF) continue;
                    if (dist[y][x][false] + 1 < dist[jump_y][jump_x][true]) {
                        dist[jump_y][jump_x][true] = dist[y][x][false] + 1;
                        coord.y = jump_y, coord.x = jump_x, coord.used_shoes = true;
                        q.push(coord);
                    }
                }
            }
        }
    }

    answer = min(dist[m][n][0] - 1, dist[m][n][1]);
    if (answer == INF - 1) answer = -1;
    return answer;
}