코딩테스트 -- 아이템 줍기 - (프로그래머스 / C++)

 

프로그래머스

문제!

---

• 아이템 줍기

문제 설명

다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.

지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.

만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.

지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.제한사항

• rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
• rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
  • 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
  • 서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
  • 문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
• charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
  • 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• itemX, itemY는 1 이상 50 이하인 자연수입니다.
  • 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• 캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.

---

요약하면 여러 사각형들이 존재하는데 그 사각형들의 가장바깥 테두리만을 이용하여

현재위치 characterX, characterY 에서 아이템의 위치 itemX, itemY 까지 이동의 최단거리를 구하는 문제입니다!

 

문제 자체는 어려워 보이지 않았습니다.

 

최단거리... 바로 dfs탐색을 이용하여 구해주면 되기에

저는 바로 2차원배열을 통해 연결되는 테두리를 체크해주었습니다!

 

첫번째 시도... 실패... 

#include <string>
#include <vector>

#include <iostream>
using namespace std;

int visit[52][52]={0};// 1~50까지 칸
int answer = 987654321;

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


void find(int a,int b,int ans_a, int ans_b, int count){//좌표 , 목적지 , 움직임
    if(a==ans_a and b==ans_b){//도착!
        answer=min(answer,count);
        return;
    }
    
    for(int i=0;i<4;i++){
        if(visit[a+dx[i]][b+dy[i]]==7){
            visit[a+dx[i]][b+dy[i]]=0;
            find(a+dx[i],b+dy[i],ans_a,ans_b,count+1);
            visit[a+dx[i]][b+dy[i]]=7;
        }
    }
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    
    
    for(int i=0;i<rectangle.size();i++){// 모든사각형 칠하기
        for(int a=rectangle[i][0];a<=rectangle[i][2];a++){
            for(int b=rectangle[i][1];b<=rectangle[i][3];b++)
                visit[a][b]=7;
        }
    }
    
    for(int i=0;i<rectangle.size();i++){// 속 파내기
        for(int a=rectangle[i][0]+1;a<=rectangle[i][2]-1;a++){
            for(int b=rectangle[i][1]+1;b<=rectangle[i][3]-1;b++)
                visit[a][b]=0;
        }
    }
    
    visit[characterX][characterY]=1;
    find(characterX,characterY,itemX,itemY,0);
    
    for(int i=0;i<50;i++){//출력
        for(int j=0;j<50;j++){
            cout<<visit[i][j]<<",";
        }
        cout<<endl;
    }
    
    return answer;
}

딱히 틀린 점은 없는것 같았지만 출력으로 테두리를 그려보니 

 

저렇게 된 부분이 붙어버립니다...

좌표단위로 배열에 저장하다보니 위의 그림으로 보았을때 (3,6), (3,5), (4,6), (4,5) 이 내점이 붙어버려서

정상적인 탐색이 불가 했습니다...

 

 

그래서 일단 좌표상에 저장하는게아닌 칸단위로 넣어 보았지만 마찬가지로 실패;;

 

머리를 싸메고 고민하고 있었는데 의외로 간단한 해결책이 있었습니다!

바로 2배로 늘려버리기!

 

모든 좌표를 2배로 증가시켜 배열에 저장시키면 위의 경우같은 오류는 피해갈수있습니다!

(배열이 좀 커지겠네요...)

 

 

다시 시작!

먼저 배열! 50칸이지만 2배로 100칸으로 늘려주고

int visit[101][101]={0};// 1~50까지 칸

 

좌표를 계산해서 배열에 넣어 줍시다.  모든좌표 x2 !

   characterX *= 2, characterY *= 2, itemX *= 2, itemY *= 2;
    
    for(int i=0;i<rectangle.size();i++){// 모든사각형 칠하기
        for(int a=rectangle[i][0]*2;a<=rectangle[i][2]*2;a++){
            for(int b=rectangle[i][1]*2;b<=rectangle[i][3]*2;b++)
                visit[a][b]=7;
        }
    }
    
    for(int i=0;i<rectangle.size();i++){// 속 파내기
        for(int a=rectangle[i][0]*2+1;a<=rectangle[i][2]*2-1;a++){
            for(int b=rectangle[i][1]*2+1;b<=rectangle[i][3]*2-1;b++)
                visit[a][b]=0;
        }
    }

이렇게 그려주면

 

제대로 그려지네요!

 

그럼 이제 탐색!

int answer = 987654321;

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

void find(int a,int b,int ans_a, int ans_b, int count){//좌표 , 목적지 , 움직임
    if(a==ans_a and b==ans_b){//도착!
        answer=min(answer,count);
        return;
    }
    
    for(int i=0;i<4;i++){
        if(visit[a+dx[i]][b+dy[i]]==7){
            visit[a+dx[i]][b+dy[i]]=0;
            find(a+dx[i],b+dy[i],ans_a,ans_b,count+1);
            visit[a+dx[i]][b+dy[i]]=7;
        }
    }
}

해주면 끝..!

 

2배로 늘린다는 생각만 빨리했어도 금방풀었을 문젠데 아쉽네요...

 

ALL

#include <string>
#include <vector>

#include <iostream>
using namespace std;

int visit[101][101]={0};// 1~50까지 칸
int answer = 987654321;

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


void find(int a,int b,int ans_a, int ans_b, int count){//좌표 , 목적지 , 움직임
    if(a==ans_a and b==ans_b){//도착!
        answer=min(answer,count);
        return;
    }
    
    for(int i=0;i<4;i++){
        if(visit[a+dx[i]][b+dy[i]]==7){
            visit[a+dx[i]][b+dy[i]]=0;
            find(a+dx[i],b+dy[i],ans_a,ans_b,count+1);
            visit[a+dx[i]][b+dy[i]]=7;
        }
    }
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    
    characterX *= 2, characterY *= 2, itemX *= 2, itemY *= 2;
    
    for(int i=0;i<rectangle.size();i++){// 모든사각형 칠하기
        for(int a=rectangle[i][0]*2;a<=rectangle[i][2]*2;a++){
            for(int b=rectangle[i][1]*2;b<=rectangle[i][3]*2;b++)
                visit[a][b]=7;
        }
    }
    
    for(int i=0;i<rectangle.size();i++){// 속 파내기
        for(int a=rectangle[i][0]*2+1;a<=rectangle[i][2]*2-1;a++){
            for(int b=rectangle[i][1]*2+1;b<=rectangle[i][3]*2-1;b++)
                visit[a][b]=0;
        }
    }
    
    visit[characterX][characterY]=1;
    find(characterX,characterY,itemX,itemY,0);
    
 
    
    return answer/2;
}

 

 

 

틀린점이 있다면 댓 달아주세요!