[Lv 2] 방문 길이

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

프로그래머스

 

이 문제는 배열의 요소를 점으로 사용하는 것이 아닌 선으로 사용해야한다.

선을 요소로 사용할 시 2차원이 아닌 3차원으로 사용해야한다.

 

선은 왕복이 가능하기 때문에 2번 방문표시를 해주어야한다.

왼쪽에서 오른쪽으로 이동할 경우

이동 하기 이전 점에서 이동한 점으로 이동과 이동한 점에서 이동하기 전의 점으로 이동을 표시해야한다.

즉, (5, 5)에서 (5, 6)으로 이동한 경우 (5, 5)에서 위로 이동한 것과 (5, 6)에서 아래로 이동한 것이 같기 떄문에 2가지를 모두 방문표시 한다는 것이다.

 

따라서 3차원 배열로 방문 배열을 생성하고

dx와 dy는 위 아래, 왼쪽 오른쪽을 묶음으로 만들어야한다.

이는 (dir + 2) % 4가 만족하도록 배열의 요소를 만들면 된다.

 

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

bool visited[11][11][4] = {false, };
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int solution(string dirs) {
    int answer = 0;
    
    int y = 5;
    int x = 5;
    
    for(int i = 0;i<dirs.length();i++){
        char c = dirs[i];
        int dir = 0;
        if(c == 'R')
            dir = 0;
        else if(c == 'U')
            dir = 1;
        else if(c == 'L')
            dir = 2;
        else
            dir = 3;
        
        int ux = x + dx[dir];
        int uy = y + dy[dir];
        
        if(ux > 10 || uy > 10 || ux < 0 || uy < 0)
            continue;
        
        int redir = (dir + 2) % 4;
        if(!visited[x][y][dir] && !visited[ux][uy][redir]){
            visited[x][y][dir] = true;
            visited[ux][uy][redir] = true;
            answer++;
        }
        y = uy;
        x = ux;
    }
    return answer;
}