코딩테스트 : 방문 길이(set)

해당 문제는 정해진 크기의 맵 내에서 움직이는 플레이어의 경로 길이를 계산하는 문제로 문제의 중점은 겹치는 경로를 어떻게 처리할 것인가 로 보인다.

내가 접근한 방법은 set을 이용하는 방법이다. set의 특징은 중복되는 데이터를 저장하지 않는다. 즉 이미 저장된 경로라면 중복되게 저장하지 않기에 set의 크기를 확인하면 경로의 길이를 확인할 수 있다.

 

Set에 대해 궁금하면 아래 글을 참고하면 자세히 설명해놨다

https://jinho082008.tistory.com/24

 

#include <string>
#include <set>
#include <map>

using namespace std;

int solution(string dirs) {
		//상하좌우 입력에 따라 움직여야할 좌표를 map으로 매핑
    map<char, pair<int, int>> m;
    //입력에 따라 반환될 x,y 좌표
    m['U'] = {0, 1}; m['D'] = {0, -1}; m['L'] = {-1, 0}; m['R'] = {1, 0}; 
    //좌표를 저장할 set, (0,0)에서 (0,1)로 이동했다면 (0,0),(0,1)과 (0,1),(0,0)을 저장해서
    //중복된 이동은 체크하지 않는다.
    set<pair<pair<int, int>, pair<int, int>>> s;
    //현재 플레이어의 좌표로 시작은 (0,0)에서 시작한다.
    pair<int, int> currentPos = make_pair(0,0);
    
    for(char ch : dirs)
    {
		    //플레이어의 다음 x좌표
        int nx = currentPos.first + m[ch].first;
        //플레이어의 다음 y좌표
        int ny = currentPos.second + m[ch].second;
        
        //움직일 위치가 맵 밖이면 행동하지 않는다.
        if(nx > 5 || ny > 5 || nx < -5 || ny < -5)
            continue;
        
        //현재 위치와 다음 좌표를 set에 저장. 중복된 경로라면 자동으로 저장이 안됨.
        s.insert({currentPos, {nx, ny}});
        //반대방향으로 이동하는 것도 같은 경로이므로 저장.
        s.insert({{nx, ny}, currentPos});
        
        //현재 좌표를 다음 좌표로 이동
        currentPos = {nx, ny};
    }
    
    //경로 한번에 반대 방향도 고려해 2개를 저장했으므로 크기 / 2
    return s.size() / 2;
}

해당 구현 방법은 만약 플레이어가 맵 밖으로 움직이려하면 for문에 continue를 하면서 현재 좌표를 업데이트 하지 않아 다음 이동에도 차질을 주지 않는다.

또한 중복된 경로를 자동으로 걸러주는 set 자료구조를 사용해 간단하게 구현하였다.