[프로그래머스] 아이템 줍기

프로그래머스: 링크

코딩테스트 연습 - 11주차_아이템 줍기

 

사실 최단 거리를 구하는 문제라서 BFS를 썼어야 이론상 조금 더 효율적인데, 그냥 DFS 재귀가 손에 익어서 DFS의 형식으로 문제를 풀었다.  그것보다 더욱 중대한 문제가 풀이 과정 중에 발생했다. 생각보다 문제는 빠르게 이해한 편이었으나, 문제의 함정을 파악하고 이를 해결하는 데 상당히 오래걸렸다.

 

상하좌우로 단순히 이동하면 되는 문제가 아니라, 경로를 잘못 파악하지 않도록 설정하는 것이 가장 중요했다. 기계적으로 문제를 풀다보면 

한 블록만 튀어나온 도형을 표현하는 데에서 어려움이 발생한다. 꼭짓점을 1로 표기하며 도형을 표기하는데, 만약 한 블록만 튀어나온 도형을 표현하면 볼록 튀어나오는 도형의 라인을 따라가는 게 아니라, 도형을 가로질러 버릴 수 있는 일이 발생한다.

하지만 위 이미지의 두 번째 줄처럼 Scale을 2배로 만들면 가로지르는 일을 방지할 수 있다. 왜냐하면 도형 내부는 -1로 표기하여서 이동 경로와 구분짓는다. 그리고 결과적으로 경로의 길이를 2로 나누면 원하는대로 경로의 길이를 얻을 수 있다. 이 때 좌표를 2배씩 처리하는 것이 중요하다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;
int map[101][101] = {0};
int visited[101][101] = {0};
// right, down, left, up
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int answer = 2500;
void dfs(int x, int y, int route, int itemX, int itemY);
int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    for(int i = 0;i < rectangle.size();i++){
        int x1 = rectangle[i][0];
        int y1 = rectangle[i][1];
        int x2 = rectangle[i][2];
        int y2 = rectangle[i][3];
        for(int x = x1 * 2;x <= x2 * 2;x++){
            map[2 * y1][x] = map[2 * y1][x] == -1 ? -1 : 1;
            map[2 * y2][x] = map[2 * y2][x] == -1 ? -1 : 1;
        }
        for(int y = 2 * y1 + 1;y < 2 * y2;y++){
            map[y][2 * x1] = map[y][2 * x1] == -1 ? -1 : 1;
            map[y][2 * x2] = map[y][2 * x2] == -1 ? -1 : 1;
        }
        for(int y = 2 * y1 + 1;y < 2 * y2;y++){
            for(int x = 2 * x1 + 1;x < 2 * x2;x++){
                map[y][x] = -1;
            }
        }
    }
    dfs(2 * characterX, 2 * characterY, 0, 2 * itemX, 2 * itemY);
    return answer / 2;
}

void dfs(int x, int y, int route, int itemX, int itemY){
    bool flag = false;
    if(route > answer) return;
    if(itemX == x && itemY == y){
        cout << route << endl;
        if(route < answer){
            answer = route;
        }
        return;
    }
    
    for(int d = 0;d < 4;d++){
        int nx = x + dx[d];
        int ny = y + dy[d];
        if(map[ny][nx] == 1 && visited[ny][nx] != 1){
            visited[ny][nx] = 1;
            dfs(nx, ny, route + 1, itemX, itemY);
            visited[ny][nx] = 0;
        }
    }
}