[C++/PGS] [PCCP 모의고사 #2] 4번 - 보물지도

 

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

프로그래머스

---

프로그래머스 PCCP 모의고사 2회 - 4번

소요시간 1시간 이상...

BFS 하드모드(?) 유형, 추정 난이도는 level 3

 

bfs 문제를 이렇게까지 꼬아서 낼 수 있다니... 삼차원배열까지 쓸 줄이야 ..

처음에 무슨 대각선 점프까지 고려를 해야하나????라는 엄청 복잡한 고민을 했었는데,

굳이 그럴 필요없이, 신발 사용 여부만 체크해서

신발 미사용 상태 -> dx/dy를 2배로 적용하면 되는 문제였다. (대각선은 고려 X)

그리고 visited[][][0]은 신발 미사용 상태로 이동했을 경우, visited[][][1]은 신발을 사용해서 이동했을 경우를 저장했음

어려웠다 🫠

 

참고용 테스트케이스)

 

 

나의 풀이

#include <string>
#include <vector>
#include <queue>
#include <climits>
#include <iostream>
using namespace std;

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int visited[1001][1001][2] = {0}; // 0: 신발 X, 1: 신발 O

bool canGo(int n, int m, int x, int y, int shoes){
    if(x<1 || y<1 || x>n || y>m) return false;
    if(visited[x][y][shoes]>0) return false;
    return true;
}

int solution(int n, int m, vector<vector<int>> hole) {
    int answer = INT_MAX;
    for(auto h:hole){
        visited[h[0]][h[1]][0] = 9; // 함정을 9로 표시
        visited[h[0]][h[1]][1] = 9;
    }
    queue<vector<int>> q; // 0:x, 1:y, 2:count, 3: 신발 사용 여부
    q.push({1,1,0,0});
    visited[1][1][0] = 1;
    visited[1][1][1] = 1;
    while(!q.empty()){
        vector<int> v = q.front();
        q.pop();
        if(v[0]==n && v[1]==m){
            if(answer > v[2]) answer = v[2];
        }
        for(int i=0; i<4; ++i){
            int nx = v[0] + dx[i];
            int ny = v[1] + dy[i];
            if(canGo(n, m, nx, ny, v[3])){
                q.push({nx,ny,v[2]+1,v[3]});
                visited[nx][ny][v[3]] = 1;
            }
        }
        if(v[3]==0){ // 신발 미사용 시
            for(int i=0; i<4; ++i){
                int nx = v[0] + 2*dx[i];
                int ny = v[1] + 2*dy[i];
                if(canGo(n, m, nx, ny, 1)){
                    q.push({nx,ny,v[2]+1,1});
                    visited[nx][ny][1] = 1;
                }
            }
        }
    }
    if(answer == INT_MAX) answer = -1;
    return answer;
}

 

모의고사 다 풀어봤더니 수료증도 준다 ㅋㅋ 🎉