[프로그래머스 Level.2] 방문 길이 (Summer/Winter Coding(~2018)) (Java)

문제 링크

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

프로그래머스

 

 

코딩테스트 연습 > Summer/Winter Coding(~2018) > 방문 길이

 

 

문제 설명

 

 

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

 

• U: 위쪽으로 한 칸 가기
• D: 아래쪽으로 한 칸 가기
• R: 오른쪽으로 한 칸 가기
• L: 왼쪽으로 한 칸 가기

 

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

 

 

예를 들어, "ULURRDLLU"로 명령했다면

 

• 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다.

• 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.

 

이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다)

 

단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.

예를 들어, "LULLLLLLU"로 명령했다면

 

• 1번 명령어부터 6번 명령어대로 움직인 후, 7, 8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.

 

이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다.

 

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

 

 

 

제한사항

• dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
• dirs의 길이는 500 이하의 자연수입니다.

 

 

입출력 예

dirs	answer
"ULURRDLLU"	7
"LULLLLLLU"	7

 

입출력 예 설명

 

 

입출력 예 #1

문제의 예시와 같습니다.

 

 

 

입출력 예 #2

문제의 예시와 같습니다.

 

 

 

 

 

나의 코드

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        boolean[][][] visited = new boolean[11][11][4]; // 3차원 배열의 마지막은 4방향 체크 (상하좌우)
        
        int x = 5;
        int y = 5;
        
        for(int i=0; i<dirs.length(); i++) {
            switch(dirs.charAt(i)) {
                case 'U' :
                    if(x + 1 <= 10) {
                        x++;
                        if(!visited[x][y][1]) {
                            // 방향성은 따지지 않고 지나간 길만 따지기 때문에 해당 방향의 반대방향도 true로 변경
                            visited[x][y][1] = true; // 위로 옮긴 지점의 아랫방향 true
                            visited[x-1][y][0] = true; // 위로 옮기기 전 지점의 윗방향 true
                            answer++;
                        }
                    }
                    break;
                case 'L' :
                    if(y - 1 >= 0) {
                        y--;
                        if(!visited[x][y][3]) {
                            visited[x][y][3] = true;
                            visited[x][y+1][2] = true;
                            answer++;
                        }
                    }
                    break;
                case 'R' :
                    if(y + 1 <= 10) {
                        y++;
                        if(!visited[x][y][2]) {
                            visited[x][y][2] = true;
                            visited[x][y-1][3] = true;
                            answer++;
                        }
                    } 
                    break;
                case 'D' :
                    if(x - 1 >= 0) {
                        x--;
                        if(!visited[x][y][0]) {
                            visited[x][y][0] = true;
                            visited[x+1][y][1] = true;
                            answer++;
                        }
                    }
                    break;
                default :
                    break;
            }
        }
        
        return answer;
    }
}

 

풀이

1. 움직인 거리를 재는 문제에서 처음 지나간 길의 거리만 재는 것으로 변형한 형태의 문제이다.
2. boolean형의 visited 배열을 통해 지나간 길을 체크해주면서 풀면 된다.
   방향이 필요 없기 때문에 좌표와 좌표 사이 길을 좌표로 삼아서  2차원 배열 boolean형 visited[10][10]을 만들어 관리해도 되지만 그냥 좌표가 편해서 3차원 배열로 관리하였다.
3. 좌표가 -5 <= x, y <= 5 이기 때문에 총 11*11개의 좌표가 생성되므로 boolean형인 visited[11][11]에다 방향성까지 추가한 3차원 배열인 visited[11][11][4]를 생성하여 판별할 수 있다. 해당 좌표에 어느 방향에서 온 건지에 대한 정보를 추가한 것이다.
4. 물론 이 문제는 방향성을 체크하는 것이 아닌 지나간 길만을 체크한 것이기 때문에 해당 도착 지점의 방향과 반대 방향으로 출발지점에도 체크를 해주어야 한다. (출발지점 -> 도착지점 (방향) true , 도착지점 -> 출발지점 (반대방향) true)
5. switch문을 통해 해당 문자에 따라 문자의 명령을 진행했을 때 좌표에서 벗어나는 것을 체크하고 방문했던 길을 체크하여 처음 방문한 길을 이동할 때만 answer를 증가시켜주면 된다.