개요

방문 길이

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

U: 위쪽으로 한 칸 가기

D: 아래쪽으로 한 칸 가기

R: 오른쪽으로 한 칸 가기

L: 왼쪽으로 한 칸 가기

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

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

접근 방식

1. 방문한 지점만 다시 안 가면 되는줄 알고 풀었다가 틀려서 다시 보니 해당 경로를 다시 가면 안되는 문제였다...

2. set을 이용해서 구현했다.

   set<pair<pair<int, int>, pair<int, int>>> s;
   

   pair을 세 개를 썼다. 첫번째는 현재 플레이어 좌표, 두번째는 가려는 목표 좌표,
   두 좌표를 묶은 pair가 두 지점의 경로이다.

3. 각 경로는 방향에 따라 구분되지 않으므로 A->B경로와 B->A경로가 같은 경로이다.

4. 다음 경로로 갈 수 있는지 판별하는 함수를 사용했다.

   bool CanReach(pair<int, int> origin, pair<int, int> target)
   {
     if (target.first < 0 || target.first >10) return false;
     if (target.second < 0 || target.second >10) return false;
     if (s.find(make_pair( origin,target) ) != s.end()) return false;
   
     //양방향으로 넣기
     s.insert(make_pair(origin, target));
     s.insert(make_pair(target, origin));
     return true;
   }
   

   첫 지점을 0,0으로하면 음수 처리해야하니 5,5로 두고 0부터 10으로 범위를 변경했다.
   

전체코드

#include <string>
#include<algorithm>
#include<set>
using namespace std;

//지점 체크 x 길을 체크해야함
set<pair<pair<int, int>, pair<int, int>>> s;

bool CanReach(pair<int, int> origin, pair<int, int> target)
{
    if (target.first < 0 || target.first >10) return false;
    if (target.second < 0 || target.second >10) return false;
    if (s.find(make_pair( origin,target) ) != s.end()) return false;

    //양방향으로 넣기
    s.insert(make_pair(origin, target));
    s.insert(make_pair(target, origin));
    return true;
}

int solution(string dirs) {
    int answer = 0;

    pair<int, int> curPos = { 5,5 };

    for (char elem : dirs)
    {
        switch (elem)
        {
        case 'L':
            if (CanReach(curPos, make_pair(curPos.first - 1, curPos.second)))
            {
                answer++;

            }
            //걸어가본길이라도 가긴가야함
            curPos.first -= 1;
            if(curPos.first<0)
                curPos.first=0;
            break;
        case 'R':
            if (CanReach( curPos,make_pair(curPos.first + 1, curPos.second)))
            {
                answer++;
            }
            curPos.first += 1;
            if(curPos.first>10)
                curPos.first=10;
            break;
        case 'D':
            if (CanReach(curPos,make_pair(curPos.first, curPos.second - 1)))
            {
                answer++;
            }
            curPos.second -= 1;
            if(curPos.second<0)
                curPos.second=0;
            break;
        case 'U':
            if (CanReach(curPos,make_pair(curPos.first, curPos.second + 1)))
            {
                answer++;
            }
            curPos.second += 1;
            if(curPos.second>10)
                curPos.second=10;
            break;

        }
        
    }
    return answer;
}

생각

더 간결한 풀이

더 생각해보니 set에 경로를 넣는 행위 자체가 중복을 제거하는 방식이다.
따라서 이동할때마다 set에 경로를 계속 넣어주기만 하면 마지막에 set에 쌓인 경로가
최종 걸어간 길이다.

또한 switch문을 사용하니 저렇게 코드가 길어졌다.
고민을 해보니 아예 map으로 char 형과 다음 좌표를 매핑해두면 더 간결해진다..

#include <string>
#include<algorithm>
#include<set>
#include <unordered_map>
using namespace std;

//지점 체크가 아니라! 길을 체크해야함
set<pair<pair<int, int>, pair<int, int>>> s;

int solution(string dirs) {
    int answer = 0;
    unordered_map<char,pair<int,int>> m;
    
    //미리 char 에 해당하는 값으로 할당해둠
    m['L'] = {-1,0};
    m['R'] = {1,0};
    m['D'] = {0,-1};
    m['U'] = {0,1};
    
    pair<int, int> curPos = { 5,5 };

    for (char elem : dirs)
    {
        int nextX = curPos.first+m[elem].first;
        int nextY = curPos.second+m[elem].second;
        
        //좌표 평면 제한
        if(nextX <0 || nextX>10|| nextY<0 || nextY>10) continue;
        
        pair<int,int> nextPos= {nextX,nextY};
        //양뱡향으로 넣기
        s.insert(make_pair(curPos,nextPos));
        s.insert(make_pair(nextPos,curPos));
        
        curPos=nextPos;
    }
    answer =s.size()/2;
    return answer;
}