[Programmers] 방문 길이(Lv.2)

풀이 소요시간 : 20분

탐색이 아니라 거의 자료구조 수준의 문제였다. 다만 이번에 set 에 구조체를 집어넣은 방식을 처음 사용해보았다. set 에 구조체를 insert 하려면 자체 비교 연산자가 필요했다. 구현하는게 번거로웠고 처음 공부해봤다.

내 코드도 더럽지는 않지만, 제출 후 풀이과정을 참고해보니 Size = 11 인 4차원 배열로 방문 체크를 하는 코드가 가장 깔끔해보였다.

전체 코드

#include <string>
#include <set>
#include <iostream>
#include <vector>
using namespace std;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
// U D R L 순서

int px;
int py;

struct Position {
    int x1;
    int y1;
    int x2;
    int y2;
    
    bool operator < (const Position& A) const
    {
        if (x1 != A.x1) {
            return x1 > A.x1;
        }
        if (y1 != A.y1) {
            return y1 > A.y1;
        }
        if (x2 != A.x2) {
            return x2 > A.x2;
        }
        return y2 > A.y2;
    }
    
};

set<Position> Set;


void Move(char C)
{
    int nx;
    int ny;
    
    switch(C) 
    {
        case 'U' : 
            nx = px + dx[0];
            ny = py + dy[0];
            break;
            
        case 'D' :
            nx = px + dx[1];
            ny = py + dy[1];
            break;
        
        case 'R' :
            nx = px + dx[2];
            ny = py + dy[2];
            break;
            
        case 'L' :
            nx = px + dx[3];
            ny = py + dy[3];
            break;          
    }
    
    if(nx < -5 || ny < -5 || nx > 5 || ny > 5) return;
    //좌표 밖을 벗어난 경우 중단.
    

    Set.insert({px, py, nx, ny});
    Set.insert({nx, ny, px, py});
    //해당 길의 좌표를 왕복 체크
    
    px = nx;
    py = ny;
    //현재 좌표 갱신
    
}

int solution(string dirs) {
    px = 0;
    py = 0;
    
    for(int i = 0; i < dirs.length(); i++)
    {
        Move(dirs[i]);
    }
    
    return Set.size() / 2;
}