[프로그래머스] 보물 지도 (PCCP 모의고사 #2 4번)

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

프로그래머스

프로그래머스 - 보물 지도 (PCCP 모의고사 #2 4번)

문제 유형 : dfs/bfs, 다이나믹 프로그래밍

문제 난이도 : Level 3

 

문제 설명

진수는 보물이 묻힌 장소와 함정이 표시된 보물 지도를 이용해 보물을 찾으려 합니다. 보물지도는 가로 길이가 n, 세로 길이가 m인 직사각형 모양입니다.

 

맨 왼쪽 아래 칸의 좌표를 (1, 1)으로, 맨 오른쪽 위 칸의 좌표를 (n, m)으로 나타냈을 때, 보물은 (n, m) 좌표에 묻혀있습니다. 또한, 일부 칸에는 함정이 있으며, 해당 칸으로는 지나갈 수 없습니다.

진수는 처음에 (1, 1) 좌표에서 출발해 보물이 있는 칸으로 이동하려 합니다. 이동할 때는 [상,하,좌,우]로 인접한 네 칸 중 한 칸으로 걸어서 이동합니다. 한 칸을 걸어서 이동하는 데 걸리는 시간은 1입니다.

진수는 보물이 위치한 칸으로 수월하게 이동하기 위해 신비로운 신발을 하나 준비했습니다. 이 신발을 신고 뛰면 한 번에 두 칸을 이동할 수 있으며, 함정이 있는 칸도 넘을 수 있습니다. 하지만, 이 신발은 한 번밖에 사용할 수 없습니다. 신비로운 신발을 사용하여 뛰어서 두 칸을 이동하는 시간도 1입니다.

이때 진수가 출발점에서 보물이 위치한 칸으로 이동하는데 필요한 최소 시간을 구해야 합니다.

 

예를 들어, 진수의 보물지도가 아래 그림과 같을 때, 진수가 걸어서 오른쪽으로 3칸, 걸어서 위쪽으로 3칸 이동하면 6의 시간에 보물이 위치한 칸으로 이동할 수 있습니다. 만약, 오른쪽으로 걸어서 1칸, 위쪽으로 걸어서 1칸, 신비로운 신발을 사용하여 위로 뛰어 2칸, 오른쪽으로 걸어서 2칸 이동한다면 총 5의 시간에 보물이 위치한 칸으로 이동할 수 있으며, 이보다 빠른 시간 내에 보물이 있는 위치에 도착할 수 없습니다.

진수의 보물지도가 표현하는 지역의 가로 길이를 나타내는 정수 n, 세로 길이를 나타내는 정수 m, 함정의 위치를 나타내는 2차원 정수 배열 hole이 주어졌을 때, 진수가 보물이 있는 칸으로 이동하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 단, 보물이 있는 칸으로 이동할 수 없다면, -1을 return 해야 합니다.

 

 

풀이

dfs + dp를 통해서 풀 수 있다.

dp[i][j][k] = i행 j열을 신비로운 신발을 k번사용해서 도달한 최소 시간으로 저장한다.(k < 2) 초기값은 1e9로 해주고, 함정이 있는곳은 또 특별한 수로 설정해준다. 나는 2e9로 했다. 그리고 dp[m-1][0][0]과 dp[m-1][0][1]은 시작지점이므로 0으로 해준다.

 

유의할 점은, 위치가 일반적인 배열에 맞춰져 있지 않다는 것이다.

이를 잘 고려해주어야 한다.

 

bfs의 로직은 다음과 같다:

큐에는 (row, col, k:신발사용횟수)를 담는다 (k < 2)

 

큐에서 요소를 하나 꺼내서 그 위치를 기준으로 상하좌우로 이동하면서 그 칸까지의 최소시간을 갱신시킨다.

만약 갱신된다면 큐에 그 위치를 삽입한다.

 

만약 현재 위치에서 신발을 사용한 적이 없다면(k=0)이라면, 상하좌우로 2칸씩 움직여서 최소시간을 갱신한다.

이 때, 갱신하는 건 dp[nx][ny][1] = dp[x][y][0]+1이다. 안 쓴 상태에서 쓴 상태로 변경한 것이기 때문이다.

 

bfs가 끝나고 dp[0][n-1][0]과 dp[0][n-1][1] 모두 1e9라면(도달하지 않았다면), -1을 반환시키고, 그게 아니라면 더 최소값을 반환시킨다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

vector<int> dx = {-1, 1, 0, 0};
vector<int> dy = {0, 0, -1, 1};

void bfs(vector<vector<vector<int>>> &dp) {
    queue<vector<int>> q;
    //{row, col, isShoeUsed};
    q.push({(int)dp.size()-1, 0, 0});
    
    while(!q.empty()) {
        auto curr = q.front();
        q.pop();
        
        int x = curr[0];
        int y = curr[1];
        int isShoeUsed = curr[2];
        
        for(int i = 0; i < 4; i++) {
        	// 상하좌우 이동
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 범위 밖을 벗어나면 중지
            if(nx < 0 || ny < 0 || nx >= dp.size() || ny >= dp[0].size()) continue;
            // 함정은 가지않음
            if(dp[nx][ny][isShoeUsed] == 2e9) continue;
            
            // 거리가 갱신된다면, 업데이트
            if(dp[nx][ny][isShoeUsed] > dp[x][y][isShoeUsed]+1) {
                dp[nx][ny][isShoeUsed] = dp[x][y][isShoeUsed]+1;
                q.push({nx, ny, isShoeUsed});
            }
        }
        
        // 만약 신발을 쓰질 않았다면, 써보자
        if(!isShoeUsed) {
            for(int i = 0; i < 4; i++) {
            	// 상하좌우 두 칸씩 점프
                int nx = x + dx[i]*2;
                int ny = y + dy[i]*2;

				// 범위를 벗어나면 중지
                if(nx < 0 || ny < 0 || nx >= dp.size() || ny >= dp[0].size()) continue;
                // 함정은 가지않음
                if(dp[nx][ny][isShoeUsed] == 2e9) continue;
				
                // 거리가 갱신된다면, 업데이트
                if(dp[nx][ny][1] > dp[x][y][isShoeUsed]+1) {
                    dp[nx][ny][1] = dp[x][y][isShoeUsed]+1;
                    q.push({nx, ny, 1});
                }
            }
        }
    }
    
}

int solution(int n, int m, vector<vector<int>> hole) {
	// m*n*2의 크기로 생성. 신발은 사용 여부만으로 갈려서 0~1(0:사용 x)
    vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(2, 1e9)));
    // 시작점은 0초
    dp[m-1][0][0] = 0;
    dp[m-1][0][1] = 0;
    
    // 함정위치 마킹하기
    for(const auto &h : hole) {
        int x = h[0]-1;
        int y = m - h[1];
        dp[y][x][0] = 2e9;
        dp[y][x][1] = 2e9;
    }
    
    // bfs
    bfs(dp);
    
    // 도달못하면 -1, 아니면 최소값 반환
    if(dp[0][n-1][0] == 1e9 && dp[0][n-1][1] == 1e9) return -1;
    return min(dp[0][n-1][0], dp[0][n-1][1]);
}