프로그래머스_아이템 줍기

문제 링크

문제 접근

좌표 평면상에 모든 도형의 둘레를 구해야하는 것을 목표로 잡았다. 그것을 하기 위한 큰 step은 다음과 같다.

1. 50 by 50 matrix 생성
2. rectangle 배열을 for문으로 돌면서 모든 점을 1로 masking
3. rectangle 배열을 for문으로 돌면서 속은 파낸다.
4. DFS로 최단 거리 구하기

2 번 3번 기능을 담당하는 함수를 따로 구현했다. 코드는 다음과 같다.

mask_path

void mask_path(vector<vector<int>>rectangle){
    //2. rectangle 배열 돌면서 모든 점을 1로 마스킹
    for(vector<int> points : rectangle){
        int x1=2*points[0];//좌측하단 x 좌표
        int y1 = 2*points[1];//좌측 하단 y 좌표
        int x2 = 2*points[2]; //우측 상단 x 좌표
        int y2 = 2*points[3]; //우측 상단 y 좌표
        for(int x = x1; x<=x2;x++){
            for(int y = y1; y<=y2; y++){
                valid[x][y] = 1; 
            }
        }
    }
    //3. rectangle 배열 돌면서 속을 파낸다.
        for(vector<int> points : rectangle){
        int x1=2*points[0];//좌측하단 x 좌표
        int y1 = 2*points[1];//좌측 하단 y 좌표
        int x2 = 2*points[2]; //우측 상단 x 좌표
        int y2 = 2*points[3]; //우측 상단 y 좌표
        for(int x = x1+1; x<=x2-1;x++){
            for(int y = y1+1; y<=y2-1; y++){
                valid[x][y] = 0;
            }
        }
    }
}

Dfs 코드는 정형적인 format으로 구현했다. 대각선 이동을 허용하지 않는 문제이기 때문에 dx,dy배열을 전역변수로 선언하여 움직임을 제어했다.

Dfs 코드는 다음과 같다.

DFS

bool valid[51][51];
bool visited[51][51];
int min_cnt = 99999999;

void dfs(int cx,int cy,int ix,int iy,int cnt){
    if(cx==ix && cy == iy){
        min_cnt = min(min_cnt,cnt);
        return;
    }
    for(int i=0;i<4;i++){
        int nx = cx + dx[i];
        int ny = cy + dy[i];
        if(valid[nx][ny] && !visited[nx][ny]){
            visited[nx][ny] = true;
            dfs(nx,ny,ix,iy,cnt+1);
            visited[nx][ny] =false;
        }
    }
}

이미 풀어본 분은 아시겠지만, 이 로직은 틀렸다. 접근 방식이 완전히 틀린 것은 아니지만 도형의 둘레가 이상해지는 edge case가 존재한다. 다음 그림을 참고해보자.

그렇다면 어떻게 방식을 바꿔야할까? 혼자 생각하지 못하여 다른 분들의 접근 방법을 참고했다. 그것은 모든 점들을 2배 곱한다음 로직을 수행하는 것이다. 물론 답을 리턴할때는 2로 나누어 출력해야한다. 정답 코드는 다음과 같다.

정답코드

#include <string>
#include <vector>
#include<iostream>
using namespace std;
/*
Maxsize = 50
그러나 2배를 곱하여 로직을 수행할 것이기 때문에 배열의 size는 102 X 102로 고정 

1. 102 by 102 matrix 생성 
2. rectangle 배열 돌면서 모든 점을 1로 마스킹
3. rectangle 배열 돌면서 속을 파낸다.
*/
bool valid[102][102];
bool visited[102][102];
int min_cnt = 99999999;

int dy[] ={-1,1,0,0};
int dx[] = {0,0,-1,1};

void mask_path(vector<vector<int>>rectangle){
    //2. rectangle 배열 돌면서 모든 점을 1로 마스킹
    for(vector<int> points : rectangle){
        int x1=2*points[0];//좌측하단 x 좌표
        int y1 = 2*points[1];//좌측 하단 y 좌표
        int x2 = 2*points[2]; //우측 상단 x 좌표
        int y2 = 2*points[3]; //우측 상단 y 좌표
        for(int x = x1; x<=x2;x++){
            for(int y = y1; y<=y2; y++){
                valid[x][y] = 1; 
            }
        }
    }
    //3. rectangle 배열 돌면서 속을 파낸다.
        for(vector<int> points : rectangle){
        int x1=2*points[0];//좌측하단 x 좌표
        int y1 = 2*points[1];//좌측 하단 y 좌표
        int x2 = 2*points[2]; //우측 상단 x 좌표
        int y2 = 2*points[3]; //우측 상단 y 좌표
        for(int x = x1+1; x<=x2-1;x++){
            for(int y = y1+1; y<=y2-1; y++){
                valid[x][y] = 0;
            }
        }
    }
}
void dfs(int cx,int cy,int ix,int iy,int cnt){
    if(cx==ix && cy == iy){
        min_cnt = min(min_cnt,cnt);
        return;
    }
    for(int i=0;i<4;i++){
        int nx = cx + dx[i];
        int ny = cy + dy[i];
        if(valid[nx][ny] && !visited[nx][ny]){
            visited[nx][ny] = true;
            dfs(nx,ny,ix,iy,cnt+1);
            visited[nx][ny] =false;
        }
    }
}
int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    mask_path(rectangle);
    dfs(2*characterX,2*characterY,2*itemX,2*itemY,0);
    return min_cnt/2;
}

좌표평면 위에서의 연산이기 때문에 이런 edge case가 존재하는 것 같다. 다음에 비슷한 문제를 풀때는 오늘의 삽질 기억하자.