[프로그래머스] 방문 길이

[프로그래머스] 방문 길이

코딩테스트 연습 - 방문 길이 | 프로그래머스

 

캐릭터가 좌우 10칸짜리 공간을 이동하는데 새로운 길을 지나가는 수를 세는 문제이다

방문노드가 아닌 방문 선분이 필요한데 check[x][y][dx][dy]라는 체크 변수를 만들었다

x, y 좌표에서 dx, dy 좌표로 이동하는 것을 체크하는 변수이다.

음수 좌표는 코드가 귀찮아지니까 전부 5씩 더해 -5,-5 좌표를 0,0으로 두고 시작좌표를 5,5로 바꾸어 진행했다.

주의할 점은 새로운 길을 찾을 때 카운트를 하는데

x,y 좌표에서 dx, dy 좌표를 체크했으면 반대로 dx, dy 에서 x, y로의 좌표도 체크를 해줘야한다.

방향만 다를 뿐 같은 길이기 때문이다.

 

#include <string>
using namespace std;

#define x_max_limit 10
#define x_min_limit 0
#define y_max_limit 10
#define y_min_limit 0

bool check[15][15][15][15]; //x1, y1에서 x2, y2로 가는 길

int solution(string dirs)
{
    int x = 5, y = 5;
    int answer = 0;
    for(auto d : dirs){
        int dx = x;
        int dy = y;
        if(d == 'L'){
            dx -= 1;
        }
        else if(d == 'R'){
            dx += 1;
        }
        else if(d == 'U'){
            dy -= 1;
        }
        else if(d == 'D'){
            dy += 1;
        }
        if(dx < x_min_limit || dx > x_max_limit || dy < y_min_limit || dy > y_max_limit)
            continue;
        if(!check[x][y][dx][dy]){
            check[x][y][dx][dy] = true;
            check[dx][dy][x][y] = true;
            answer += 1;
        }
        x = dx;
        y = dy;
    }
    return answer;
}