[PCCP 모의고사 #2] 보물 지도 c++ (bfs)

문제 링크

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

프로그래머스

 

문제 풀이

이 문제를 보면 바로 bfs를 통한 최단거리 해결책이 떠올랐을 것이다.(1칸 이동의 비용이 '1'로 고정된 단위 길이이기에, 다익스트라를 사용할 필요가 없다.)

이 문제는 약간의 변형으로, 일회성으로 2칸을 이동가능한 "신발" 이 존재하기에, 이를 고려해야한다.

일반적으로 point가  2개의 좌표값, 거리만 있는 것에 반해, 여기서는 일회성 아이템인 "신발" 의 사용 유무도 체크하며 bfs로 완전 탐색을 돌면 된다.

 

 

정답 코드

#include <string>
#include <vector>
#include<queue>
#include<iostream>
using namespace std;
#include<string.h>
int dw[4]={1,-1,0,0};
int dh[4]={0,0,1,-1};
struct p{
    int w;
    int h;
    int dist;
    bool use;
};
int visit[2000][2000][2]; //신발 사용 & 미사용 상태 구분하자!
int arr[2000][2000];

int solution(int n, int m, vector<vector<int>> hole) {
    int answer = 98765432;
    
    queue<p> qu;
    qu.push({0,0,0,false});
    for(auto a:hole){
        arr[a[1]-1][a[0]-1]=1;//구멍
    }
    if(arr[m-1][n-1]==1||arr[0][0]==1)return -1;
    while(!qu.empty()){
        p now=qu.front();
        qu.pop();
        if(now.w==m-1&&now.h==n-1){
            if(answer>now.dist)
                 answer=now.dist;
             break;
        }
        for(int i=0;i<4;i++){
            int nw=now.w+dw[i],nh=now.h+dh[i];
            if(0<=nw&&nw<m&&0<=nh&&nh<n){
                if(!visit[nw][nh][now.use]&&arr[nw][nh]==0){
                    visit[nw][nh][now.use]=1;// 여기서 [][][0] 하는 실수 발생!
                    qu.push({nw,nh,now.dist+1,now.use});
                }
            }
            if(now.use)continue;//이미 신발 사용
            int double_w=nw+dw[i],double_h=nh+dh[i];
            if(0<=double_w&&double_w<m&&0<=double_h&&double_h<n){
                if(!visit[double_w][double_h][1]&&arr[double_w][double_h]==0){                     
                		visit[double_w][double_h][1]=1;
                        qu.push({double_w,double_h,now.dist+1,true});
                }
            }
        }
    }
    if(answer==98765432)answer=-1;
    return answer;
}

 

 

주의 사항

 

bfs 탐색에는 "왔던 길을 다시 돌아갈 필요가 없다" 너비 우선 탐색이기에, 뒷순위에 오는 것은 더 깊은 depth, 즉 더 많은 타일을 거쳐서 온 값이기에, 단위길이가 cost인 문제의 특성 상, 먼저 온 값이 최솟 값이다.

이는 "신발" 이라는 특수한 아이템이 들어와도 변함 없다. 

하지만, 어떠한 타일에 진입한 시점에서, "신발을 이미 사용해서 해당 타일에 도착한 것" 그리고 "신발을 사용하지 않고 도착한 것"은 엄연히 다른 케이스이다. 이후에 신발 사용량을 모두 소진해 도착하지 못하는 경우가 생기거나, 이후에 더 효율적이게 신발을 사용할 수 도 있는 일이다. 그렇기에, 아래와 같이, visit 배열에 좌표만으로 표기하지 않고 아래와 같이 구분해주었다.

 

int visit[2000][2000][2]; //신발 사용 & 미사용 상태 구분.  
// visit[a][b][0]: 신발 사용하지 않은 상태로  b,a 도착
// visit[a][b][1]: 신발 사용하고 b,a 도착
		............
                if(!visit[nw][nh][now.use]&&arr[nw][nh]==0){
                    visit[nw][nh][now.use]=1;// 여기서 [][][0] 하는 실수 주의!
       				...............
            	if(now.use)continue;//이미 신발 사용시 신발 사용 불가!
            
                if(!visit[double_w][double_h][1]&&arr[double_w][double_h]==0){      
                		visit[double_w][double_h][1]=1;
                 		.....