프로그래머스 - 방문길이

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

프로그래머스

---

문제 설명

11x11 크기의 맵이 있고 언제나 중앙에서 시작합니다. 아래와 같은 4가지 명령어가 있고, 좌표평면의 경계를 넘어가는 명령을 무시할 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하세요.

U : 위로 1칸 가기, D : 아래로 1칸 가기, 'L' : 왼쪽으로 1칸 가기, 'R' 오른쪽으로 1칸 가기

---

아이디어

11x11 배열에 들어오는 방향을 상하좌우를 둬서 특정 지점에 어느 방향으로 들어오는 길이 사용됐는지를 체크합니다.
이전 있던 자리와 다음 자리에 길이 공유되기에 이전 있던 자리에서 나간 방향도 같이 기록해야 합니다.

---

코드

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

vector<vector<vector<int>>> visited(11, vector<vector<int>>(11, vector<int>(4, 0))); //0 : left, 1 up, 2 right, 4 down comefrom

map<char, pair<int, int>> cmd = {{'U', {-1, 0}}, 
                                 {'D', {1, 0}}, 
                                 {'L', {0, -1}}, 
                                 {'R', {0, 1}}};
map<char, int> checkDir = {{'L', 0}, {'U', 1}, {'R', 2}, {'D', 3}};
map<char, char> oppositeDir = {{'L', 'R'}, {'R','L'}, {'U','D'}, {'D','U'}};

int solution(string dirs) {
    int answer = 0;
    pair<int, int> cur = {5, 5};
    for(const auto& dir : dirs)
    {
        int nextX = cur.x + cmd[dir].x;
        int nextY = cur.y + cmd[dir].y;
        if(nextX < 0 || nextX > 10 || nextY < 0 || nextY > 10)
            continue;
        
        if(visited[nextX][nextY][checkDir[dir]] == 0 && visited[cur.x][cur.y][checkDir[oppositeDir[dir]]] == 0)
        {
            answer++;
            visited[nextX][nextY][checkDir[dir]] = 1;
            visited[cur.x][cur.y][checkDir[oppositeDir[dir]]] = 1;
        }
        cur = {nextX, nextY};
    }
    
    return answer;
}

메모리 4.14MB, 시간 0.02ms

---

다른 사람의 풀이에서 가장 직관적인 방법은 [현재x][현재y][다음x][다음y]로 11x11x11x11 배열로 어느 지점에서 어느 지점으로 갔는지 체크가 가장 직관적인 것 같습니다.