[C++/PGS] [PCCP 기출문제] 4번 - 수레 움직이기

 

문제

https://school.programmers.co.kr/learn/courses/19344/lessons/242261#

https://school.programmers.co.kr/learn/courses/30/lessons/250134

프로그래머스

 

---

 

프로그래밍 강의 中 PCCP 기출문제 : 4번 수레 움직이기 (프로그래머스 레벨 3 / 정답률 18% 문제..)

소요시간 약 55분 (힌트 참고함)

dfs, 백트래킹 문제, 난이도 level 3-4 추정

 

백트래킹 구현.....참 힘들다....

red, blue 두 개를 동시에 이동시키니까 코드 길이도 2배 이벤트~~🤯🤯

본인이 아니라 다른 점이 방문했던 곳으로는 이동이 가능하기 때문에 visited 배열도 따로 필요함

 

참고로, 테스트케이스 4번과 7번 등을 계속 틀리는 경우는 아래 주의사항 확인하기!!!

 

1. red 말고 blue를 먼저 움직이는 경우도 고려되는지

2. dfs 분기 이전에 조건처리 잘 했는지 (같은 칸으로 이동하거나, 서로 자리를 바꾸는 경우)

 

 

나의 풀이

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

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int n; int m;
int answer = INT_MAX;

int rVisited[5][5] = {0,};
int bVisited[5][5] = {0,};
pair<int,int> redStart;
pair<int,int> redEnd;
pair<int,int> blueStart;
pair<int,int> blueEnd;

bool canGo(int x, int y, bool isRed){
    if(x<0 || y<0 || x>=n || y>=m) return false;
    if(isRed){
        if(rVisited[x][y]>0) return false;
    }
    else {
        if(bVisited[x][y]>0) return false;
    }
    return true;
}

void dfs(pair<int,int> r, pair<int,int> b, int count){ // 현재 위치, 횟수
    if(r == redEnd && b == blueEnd){
        if(answer>count) answer = count;
        return;
    }
    if(answer < count) return;
    
    vector<pair<int,int>> rv; // 이동가능한 칸을 저장
    vector<pair<int,int>> bv;
    // r이 이동가능할 경우를 저장, end지점이라면 고정
    if(r != redEnd){
        for(int i=0; i<4; ++i){
            int rx = r.first + dx[i];
            int ry = r.second + dy[i];
            if(canGo(rx, ry, true)){
                rv.push_back({rx, ry});
            }
        }
    }
    else rv.push_back(redEnd);
    // b가 이동가능할 경우를 저장, end지점이라면 고정
    if(b != blueEnd){
        for(int i=0; i<4; ++i){
            int bx = b.first + dx[i];
            int by = b.second + dy[i];
            if(canGo(bx, by, false)){
                bv.push_back({bx, by});
            }
        }
    }
    else bv.push_back(blueEnd);
    // dfs 및 백트래킹 시행
    for(auto rr: rv){
        for(auto bb: bv){
            if(rr == bb) continue; // 같은 칸으로 X
            if(rr == b && r == bb) continue; // 자리바꾸기 X
            rVisited[rr.first][rr.second] = 1;
            bVisited[bb.first][bb.second] = 2;
            dfs(rr, bb, count+1);
            rVisited[rr.first][rr.second] = 0;
            bVisited[bb.first][bb.second] = 0;
        }
    }
}

int solution(vector<vector<int>> maze) {
    n = maze.size();
    m = maze[0].size();
    
    // 각 좌표와 함정 위치를 저장
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            switch(maze[i][j]){
                case 1:
                    redStart = {i,j};
                    rVisited[i][j] = 1;
                    break;
                case 2: 
                    blueStart = {i,j};
                    bVisited[i][j] = 2;
                    break;
                case 3:
                    redEnd = {i,j}; break;
                case 4:
                    blueEnd = {i,j}; break;
                case 5:
                    rVisited[i][j] = 5;
                    bVisited[i][j] = 5; break;
            }
        }
    }
    
    // dfs 진입
    dfs(redStart, blueStart, 0);
    // 최솟값이 갱신되지 않았다면 0을 리턴
    if(answer == INT_MAX) answer = 0;
    return answer;
}