프로그래머스 방문 길이

문제 바로가기

(0,0)에서 시작해서 상하좌우로 이동 명령이 적혀있는 명령어가 들어왔을 때 처음 지나가게 되는 경로의 수를 구하면 되는 문제다.

접근방식

우선 이 경로를 이미 지났다를 어떻게 표현해야할지 고민했었다. 보통 visited배열을 선언해서 하곤했는데 이거는 2차원 좌표이다보니 배열을 쓰기도 뭔가 애매했었다. 끝내 찾은 방법은 좌표값 이용하기였다.
예를 들어서 (0,0)에서 'U'명령어를 받으면 (0,1)이 되는데 좌표값을 합쳐서 즉, 0001을 만들어서 경로를 이미 지났음을 표현해줬다. 자료구조로는 map을 사용해주었고 map안에 경로값이 있는지 없는지를 통해 방문경로의 수를 세주었다.

이렇게만 하면 문제가 풀릴 줄 알았으나... 하나 빼먹은게 있었다.

( 1 , 2 ) -> ( 2 , 2 ) 로 이동했다면 1222가 map에 들어갔을 것이다. 그런데,
( 2 , 2) - > ( 1 , 2 ) 의 경로 값이 나온다면 사실 순서만 바뀐것이지 이미 지나온 경로이다. 그러나 map에는 2212의 값이 없으므로 경로 횟수가 세지는 결과가 발생했었다.
그래서 이동할때마다 반대방향의 경로값도 map에 추가해주는 과정을 넣어주었고 문제를 맞출 수 있었다.

#include <string>
#include <map>

using namespace std;

map <string,int> fstvstroot;

int solution(string dirs) {
    int x=0,y=0,cnt = 0;
    for(int i = 0; i < dirs.length();i++){
        string a ="", b="";
        if(dirs[i] == 'U'){
            if(y == 5) continue;
            a = to_string(x) + to_string(y);
            b = to_string(x) + to_string(++y);
        }
        else if(dirs[i] == 'L'){
            if(x == -5) continue;
            a = to_string(x) + to_string(y);
            b = to_string(--x) + to_string(y);
        }
        else if(dirs[i] == 'R'){
            if(x == 5) continue;
            a = to_string(x) + to_string(y);
            b = to_string(++x) + to_string(y);
        }
        else if(dirs[i] == 'D'){
            if(y == -5) continue;
            a = to_string(x) + to_string(y);
            b = to_string(x) + to_string(--y);
        }
        if(fstvstroot[a+b] == 0){
            fstvstroot[a+b] = 1;
            fstvstroot[b+a] = 1;
            cnt++;
        }
    }
    return cnt;
}