프로그래머스/윈터코딩2018기출/방문길이/해시를 이용한 풀이/C++

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

알고리즘 연습 - 방문 길이 | 프로그래머스

내 기준으로는 호락호락하지 않은 문제다.

핵심은 단순 경로가 아니고, 중복되지 않은 '경로 궤적'의 길이를 구해야 한다는 점이다.

이를 구현하기 위해 한 점에서 이동을 할 때 시작점 -> 도착점, 도착점->시작점 이 두 가지 경로에 대해 방문이 되지 않은 경우만, 경로의 길이에 합산하였다. 

그리고, 굳이 -5~5값을 갖는 범위로 하지 않고, 0~10 까지의 좌표를 갖는 좌표계로 옮겨서 생각하였다 (그럼 시작점도 0,0 에서 5,5로 이동될 것이다.)

저 시작점 -> 도착점, 도착점->시작점은 map과 pair를 사용하여 

map<pair<pair<int,int>, pair<int,int>>, int> dist_check;로 구현하였다.

---

[구현코드]

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

int solution(string dirs){
    int answer = 0;
    const char dir[] = {'U','D','R','L'};
    const int dy[] = {1,-1,0,0};
    const int dx[] = {0,0,1,-1};
    map<pair<pair<int,int>, pair<int,int>>, int> dist_check;
    pair<int, int> now = make_pair(5,5);
    for(int i = 0; i < dirs.length(); i++){
        for(int m = 0; m < 4; m++){
            if(dirs[i] == dir[m]){
                int next_y = now.first+dy[m];
                int next_x = now.second+dx[m];
                if(next_y >= 0 && next_y <= 10
                   &&next_x >= 0 && next_x <=10){
                    //시작점 -> 도착점, 도착점 -> 시작점 모두 체크되지 않은 경우만 거리로 추가한다.
                    if(dist_check[make_pair(now,make_pair(next_y,next_x))] == 0 &&
                       dist_check[make_pair(make_pair(next_y,next_x),now)] == 0){
                        answer++; //거리 추가
                        dist_check[make_pair(now,make_pair(next_y, next_x))] = 1; // 시작점->도착점 경로 체크
                        now = make_pair(next_y, next_x); // 도착점을 현 좌표로 갱신
                    }
                    else{
                        dist_check[make_pair(now,make_pair(next_y, next_x))] = 1; // 시작점->도착점 경로 체크
                        now = make_pair(next_y, next_x); // 도착점을 현좌표로 갱신
                    }
                    
                }
                else{
                    continue;
                }
            }
        }
    }
    return answer;
}