[프로그래머스] 아이템 줍기 (C++)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/87694

코딩테스트 연습 - 11주차

1. 주의할 점

- 직사각형을 어떤 방식으로 표현할 것인가?

- 좌표를 어떻게 나타낼 것인가?

- 경계를 어떻게 찾을것인가?

 

2. 구현

- 직사각형을 Arr[][] 배열에 담으며, 경계뿐만 아니라 내부도 1로 채워넣는다. 이때, 좌표를 표현해야하기 때문에 가로 세로를 2배씩 늘린다(일반적으로 하면 해당 면으로 표현되어 겹칠 수 있다. ex TC 1번)

- Num에 직사각형의 가로/세로의 최대값을 저장하여 최대 범위를 미리 구한다

- 경계만을 타고 움직여야 한다 → 미로찾기에서 힌트를 얻었다.

- 미로찾기의 경우, 한 손을 벽으로 짚으면서 계속 가다보면 출구를 찾을 수 있다 → 오른손으로 벽을 짚고 앞으로 전진한다

- 그렇다면 직진 or 꺽는 부분은 어떻게 처리해야 하는가? 진행중 ↔ 시작점에서의 구분이 필요하다. 공통적인 부분으로는 해당 구역에서 인접한 칸(상하좌우)에 적힌 1의 수를 구한다 → Cnt에 저장

1: 직사각형

- 파란구역(코너): Cnt=2

- 빨간구역(변) : Cnt=3

- 노란구역(2개의 직사각형이 교차되는 부분): Cnt=4

 

[진행중일 때 - DFS()]

- 코너인 경우, 오른손으로 벽을 짚고 가기 때문에 시계방향으로 90도 회전

- 변인 경우, 진행방향 그대로 직진(위로)

- 교차로인 경우, 반시계방향으로 90도 회전

- 이때, halfLen에는 목표지점까지의 거리를, totLen에는 둘레를 구한다

 

[시작점일 때 - findPathByRightHand()]

- Check[8]: 8방향 중에서 직사각형인 부분 True로 저장

- 코너나 변인 경우, Check[]를 통해 어떤 부분이 직사각형인지 판단하고 시작방향을 정한다

- 교차로인 경우, 대각선 방향도 검사하여 직사각형이 아닌 0인 부분을 탐색하여 시작방향을 정한다.

 

- HalfLen과 TotLen-HalfLen을 비교하여 오른손/왼손으로 벽을 짚고 목적지까지 갈때 걸리는 시간을 비교할 수 있다

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
struct info{
    int y,x,val,dir;
};
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={-1,0,1,0,-1,1,1,-1};
int arr[101][101];
bool check[8]={false,};
int num=0,fx,fy,totLen,halfLen;

void dfs(int y, int x, int dir, int dist, int ey, int ex) {
	if (y == fy && x == fx) {
		totLen = dist/2;
		return;
	}
	if (y == ey && x == ex)  halfLen = dist/2;
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx > 0 && ny > 0 && nx <= num && ny <= num && arr[ny][nx] == 1)
			cnt++;
	}
	if (cnt == 2) dir = (dir + 1) % 4;     //꼭지점
	else if (cnt == 4)  dir = (dir + 3) % 4;   //교차로
	dfs(y + dy[dir]*2, x + dx[dir]*2, dir, dist + 2, ey, ex);
}

void findPathByRightHand(int sy, int sx, int ey, int ex){
    int cnt=0,dir,dirTot=0;
    for(int i=0;i<4;i++){
        int nx = sx+dx[i];
        int ny = sy+dy[i];
        if(nx>0 && ny>0 && nx<=num && ny<=num && arr[ny][nx]==1){
            cnt++;
            check[i]=true;
            dirTot+=i;
        }
    }
    if(cnt==2){     //꼭지점
        if(check[0] && check[1]) dir=0;
        else if(check[1] && check[2]) dir=1;
        else if(check[2] && check[3]) dir=2;
        else dir=3;
    }
    else if(cnt==3){        //한 변의 중간(아래 문자는 Check가 true인곳 표시)
        if(dirTot==3) dir=0;        //ㅏ
        else if(dirTot==6) dir=1;   //ㅜ
        else if(dirTot==5) dir=2;   //ㅓ
        else dir=3;                 //ㅗ
    }
    else{       //두 교점의 교차지점    +
        int idx;
        //빈곳 찾기
        for(int i=4;i<8;i++){
            int nx = sx+dx[i];
            int ny = sy+dy[i];
            if(nx>0 && ny>0 && nx<=num && ny<=num && arr[ny][nx]==0){
                idx=i;
                break;
            } 
        }
        if(idx==4) dir=1;
        else if(idx==5) dir=2;
        else if(idx==6) dir=3;
        else dir=0;
    }
    dfs(sy+dy[dir]*2,sx+dx[dir]*2,dir,2,ey,ex);
}

int solution(vector<vector<int>> rectangle, int sx, int sy, int ex, int ey) {
    int answer = 0;
	sx *= 2;
	sy *= 2;
	ex *= 2;
	ey *= 2;
	fy = sy;
	fx = sx;
	for (int i = 0; i < rectangle.size(); i++) {
		int lx = rectangle[i][0] * 2;
		int ly = rectangle[i][1] * 2;
		int rx = rectangle[i][2] * 2;
		int ry = rectangle[i][3] * 2;
		num = max(num, rx);
		num = max(num, ry);
		for (int y = ly; y <= ry; y++)
			for (int x = lx; x <= rx; x++)
				arr[y][x] = 1;
	}
	findPathByRightHand(sy, sx, ey, ex);
    return answer = min(halfLen,totLen-halfLen);
}