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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

좌표를 이동시키면서, 중복되지 않은 이동경로의 개수를 세는 문제이다.

이동하며 특정 루트를 방문했었는지 확인하는 과정이 필요하다. 방문했던 좌표 (x, y)를 저장하는 vector나 set을 쓸 수도 있지만, 주어진 좌표평면의 크기가 작아 bool 타입의 배열을 선언하면 간단히 처리할 수 있다.

 

주어진 문자열을 순회하면서, U, D, L, R에 따라 새로운 이동 좌표를 구한다.

만약, 새 좌표가 주어진 범위를 넘어간다면 이를 무시하라고 했으므로 아무런 일도 없었던 것처럼 넘어간다.

새 좌표가 주어진 범위 내에 있을 때 좌표를 이동하고, 해당 경로를 방문한적이 없다면 cnt 변수를 1 증가시킨다.

모든 문자를 순회한 후 최종 cnt 값을 리턴하면 정답이다.

 

주의할 것

문제에서는 음수의 좌표가 주어졌지만, 배열의 인덱스는 음수가 될 수 없다.

따라서, 모든 이동 좌표에 HALF(5)를 더해 양수가 되도록 해주어야 한다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second
#define HALF 5

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

bool visited[15][15][15][15];

bool OOB(int x, int y) {
    return x < 0 || x > 10 || y < 0 || y > 10;
}

int solution(string dirs) {

    int cnt = 0;
    int bfx = HALF;
    int bfy = HALF;

    for (auto d : dirs) {
        int curx = bfx;
        int cury = bfy;
        for (int i=0; i<4; i++) {
            if ("UDLR"[i] != d) continue;
            curx += dx[i];
            cury += dy[i];
        }

        if (OOB(curx, cury)) continue; //새로운 좌표가 범위를 벗어나는 경우 무시
        if (!visited[bfx][bfy][curx][cury]) { //이전에 방문한적 없는 길이라면 cnt 증가
            cnt++;
            visited[bfx][bfy][curx][cury] = true;
            visited[curx][cury][bfx][bfy] = true;
        }

        bfx = curx; //최신 좌표 업데이트
        bfy = cury;
    }

    return cnt;
}