[Programmers] 방문길이

방문길이

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

• U: 위쪽으로 한 칸 가기
• D: 아래쪽으로 한 칸 가기
• R: 오른쪽으로 한 칸 가기
• L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.
명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

제한사항

• dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
• dirs의 길이는 500 이하의 자연수입니다.

풀이

1. map을 U, D, R, L에 해당하는 값으로 선언했고 {x, y}로 작성
2. nxt의 x, y 좌표가 모두 범위가 아니면 넘어감
3. v에 해당 좌표를 지나간 적이 없으면 지나간 양쪽 좌표를 2번 저장하고 경로+1
   {시작x, 시작y, 끝x, 끝y}
   {끝x, 끝y, 시작x, 시작y}
4. 현재 좌표를 cur=nxt로 바꿔 줌

코드

#include <bits/stdc++.h>
using namespace std;

map<char,vector<int>> m = {
    {'U',{0,1}}, {'D',{0,-1}}, {'R',{1,0}}, {'L',{-1,0}}
};
vector<vector<int>> v;
int solution(string dirs) {
    vector<int> cur={0,0};
    int answer = 0;

    for(char c:dirs){
        vector<int> nxt(2);
        nxt[0] = cur[0]+m[c][0];
        nxt[1] = cur[1]+m[c][1];
        if(nxt[0]>5 || nxt[0]<-5 || nxt[1]>5 || nxt[1]<-5) continue; // OOB

        vector<int> tmp1 = {cur[0], cur[1], nxt[0], nxt[1]};
        vector<int> tmp2 = {nxt[0], nxt[1], cur[0], cur[1]};
        if(find(v.begin(), v.end(), tmp1)==v.end()){ // 처음 가는 길
            v.push_back(tmp1);
            v.push_back(tmp2);
            answer++;
        }
        cur = nxt;
    }
    return answer;
}

정리

다른 사람들의 풀이를 보고 vector 대신 set으로 하고 경로 개수를 세지 않아도 된다는 것을 알았다.

#include <bits/stdc++.h>
using namespace std;

map<char,vector<int>> m = {
    {'U',{0,1}}, {'D',{0,-1}}, {'R',{1,0}}, {'L',{-1,0}}
};
set<vector<int>> s;
int solution(string dirs) {
    vector<int> cur={0,0};

    for(char c:dirs){
        vector<int> nxt(2);
        nxt[0] = cur[0]+m[c][0];
        nxt[1] = cur[1]+m[c][1];
        if(nxt[0]>5 || nxt[0]<-5 || nxt[1]>5 || nxt[1]<-5) continue; // OOB

        s.insert({cur[0], cur[1], nxt[0], nxt[1]});
        s.insert({nxt[0], nxt[1], cur[0], cur[1]});
        cur = nxt;
    }
    return s.size()/2;
}