[프로그래머스] 수레 움직이기 C++

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

프로그래머스

풀이 방법

주의할 점 dfs 백트레킹

백트레킹에서 전역 변수를 최대한 덜 사용하고 문제를 최대한 분리하기 위해 함수의 인자로 넘길 것

 

최대 크기가 4x4 밖에 안되므로 완전 탐색 + 백트레킹으로 생각해 볼 수 있다.

 

조건에 맞게 서로 교차되는 경우, 같은 곳에 이동하는 경우, 방문한 곳에 다시 방문하는 경우를 하나씩 잘 구별해 주면 된다.

 

또한 공이 도착하지 않은 경우에만 이동시켜주어야 한다. 이 부분에서 크게 실수를 했다.

if (g_maze[ry][rx] != 3) { // 도착하지 않은 경우만 진행한다.            
            nry += dy[i];
            nrx += dx[i];
            // 가능한지 체크
        if (!check(nry, nrx) || r_visited[nry][nrx] == 1 ) continue;
        
        r_visited[nry][nrx] = 1;
}

if (g_maze[ry][rx] != 3) { // 도착하지 않은 경우만 진행한다.            
            nry += dy[i];
            nrx += dx[i];                    
}
        if (!check(nry, nrx) || r_visited[nry][nrx] == 1 ) continue;
        
        r_visited[nry][nrx] = 1;

두 코드의 차이점을 찾지 못했다.

 

1번째 코드는 공이 빨간 공이 도착했을 때 공을 이동시키지 않으면서 파란 공만 계속해서 깊게 dfs를 수행할 수 있다.

하지만 2번째 코드는 빨간 공이 도착하게 된다면, 파란 공은 딱 한 번만 상하좌우로 이동시킬 수 있다는 점이다.

 

코드

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <memory.h>

using namespace std;

int b_visited[4][4];
int r_visited[4][4];
int n, m;
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};
vector<vector<int>> g_maze;


bool check(int y, int x) {
    // 범위를 벗어나는 경우
    if (y < 0 || y >= n || x < 0 || x >= m) return false; 
    // 벽으로 이동하는 경우
    if (g_maze[y][x] == 5) return false;

    return true;
}

int dfs(int cnt, int ry, int rx, int by, int bx) {            
    
    if (g_maze[ry][rx] == 3 && g_maze[by][bx] == 4) return cnt;
    int ret = 987654321;    
    for (int i =0;i < 4;i++) {        
        int nry = ry;
        int nrx = rx;
        if (g_maze[ry][rx] != 3) { // 도착하지 않은 경우만 진행한다.            
            nry += dy[i];
            nrx += dx[i];
            // 가능한지 체크
        if (!check(nry, nrx) || r_visited[nry][nrx] == 1 ) continue;
        
        r_visited[nry][nrx] = 1;
        }
        
        for (int j = 0;j < 4;j++) {
            int nby = by;
            int nbx = bx;
            if (g_maze[by][bx] != 4) {                       
                nby += dy[j];
                nbx += dx[j];
                if (!check(nby, nbx) || b_visited[nby][nbx] == 1) continue;
            }
            

            // 같은 곳을 방문하는 경우
            if (nry == nby && nrx == nbx) continue;
            
            // 서로 크로스 되는 경우
            if (ry == nby && rx == nbx && by == nry && bx == nrx) continue;
                                   
            b_visited[nby][nbx] = 1;            
            // 실제로 이동
            ret = min(ret, dfs(cnt + 1, nry, nrx, nby, nbx)); // 최소를 찾자
            b_visited[nby][nbx] = 0;
        }
        r_visited[nry][nrx] = 0;
    }
        
    return ret;    
}        
 
int solution(vector<vector<int>> maze) {
    memset(r_visited, 0, sizeof(r_visited));
    memset(b_visited, 0, sizeof(b_visited));
    int rx, ry, bx, by;
    int answer = 0;
    n = maze.size(), m = maze[0].size();    
    for (int i = 0;i < maze.size();i++) {
        for (int j = 0;j < maze[0].size();j++) {
            if (maze[i][j] == 1) {
                ry= i, rx = j;
            }
            else if (maze[i][j] == 2) {
                by = i, bx = j;
            }
        }
    }
    g_maze = maze;
    r_visited[ry][rx] = 1;
    b_visited[by][bx] = 1;
    answer = dfs(0, ry, rx, by, bx);
    if (answer == 987654321) return 0;
    return answer;
}