방문 길이

programmers.co.kr/learn/courses/30/lessons/49994

코딩테스트 연습 - 방문 길이

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

int dx[] = {-1,1,0,0};  //위, 아래, 왼, 오
int dy[] = {0,0,-1,1};



typedef struct{
    int x;
    int y;
    char way; 
}loc;   //set안에 구조체안됨 , map key 값으로 구조체 안됨, 대신 큐안에는 구조체 들어가도 됨. 
        //set과 map 안에 구조체가 안되므로 pair을 써야함. 

int solution(string dirs) {
    
    int answer = 0;
    set<set<pair<int,int>>>check;
 
    int x = 0;
    int y = 0;
 
    for(int i=0; i<dirs.size(); i++){
        
        int nx,ny;
        if(dirs[i]=='U'){
            nx = x+ dx[0];
            ny = y + dy[0];
        }
        else if(dirs[i]=='D'){
             nx = x+dx[1];
             ny = y+dy[1];
        }
        else if(dirs[i]=='L'){
             nx = x+dx[2];
             ny = y+dy[2];
        }
        else if(dirs[i]=='R'){
             nx = x+dx[3];
             ny = y+dy[3];
        }
        if(nx>=-5 && nx<=5 && ny>=-5 && ny<=5){
            set<pair<int,int>> elem;
            elem.insert(make_pair(x,y));
            elem.insert(make_pair(nx,ny));
            if(check.find(elem)==check.end()){
                check.insert(elem);
                answer++;
            }
             x = nx;
             y = ny;
         
        }
    }
    return answer;
}

- pair와 set을 이용해서 기존에 방문한 루트인지를 알아내면 된다.