Programmers Level 2: 방문 길이(C++)

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

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

풀이법

1) 단순히 구현으로 풀 수 있는 문제이다.

2) 3차원 방문 배열을 생각해 내어서 문제를 해결하였다.

(3차원 배열을 활용하지 않을 시에 test case 8~20번이 막히는 현상이 발생한다.)

0: 왼쪽, 1:위쪽, 2:오른쪽, 3:아랫쪽 으로 임의로 정의했다.

3) 보다 편한 구현을 위해 제일 좌측 우측 상단을 (0,0)으로 재 정의하여 문제를 해결했다.

 

대표적인 예시를 들자면, L의 경우

                visited[x][y-1][2]=true;
                visited[x][y][0]=true;

기존의 위치에서는 좌측으로 이동하지만, 새롭게 이동할 곳에서는 우측 선이 그어짐을 알 수 있다.

보다 자세한 것을 코드를 보며 이해한다면 충분히 알 수 있으리라 생각한다.

(생각해 낸 Hidden Case는 맨 밑에 첨부하였다.)

#include <string>

using namespace std;

bool visited[11][11][4];
int solution(string dirs) {
    int answer = 0;
    int x=5;
    int y=5;
    for(int i=0; i<dirs.size();i++)
    {
        if(dirs[i]=='L')
        {
            if(y-1<0)
                continue;
            if(!visited[x][y-1][2]&&!visited[x][y][0])
            {
                visited[x][y-1][2]=true;
                visited[x][y][0]=true;
                answer++;
            }
            y=y-1;
        }
        else if(dirs[i]=='U')
        {
            if(x-1<0)
                continue;
            if(!visited[x-1][y][3]&&!visited[x][y][1])
            {
                visited[x-1][y][3]=true;
                visited[x][y][1]=true;
                answer++;
            }
            x=x-1;
        }
        else if(dirs[i]=='R')
        {
            if(y+1>=11)
                continue;
            if(!visited[x][y+1][0]&&!visited[x][y][2])
            {
                visited[x][y+1][0]=true;
                visited[x][y][2]=true;
                answer++;
            }
            y=y+1;
        }
        else
        {
            if(x+1>=11)
                continue;
            if(!visited[x+1][y][1]&&!visited[x][y][3])
            {
                visited[x+1][y][1]=true;
                visited[x][y][3]=true;
                answer++;
            }
            x=x+1;
        }
    }
    return answer;
}

Hidden Case

"ULURRDLLUURDLLL" : 12

"LRLR": 1