프로그래머스[Java] - (Level3)방문 길이

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

프로그래머스

코드

class Solution {
    // U,D,R,L - 위,아래,오른쪽,왼쪽 순
    public static int[] dx = {0, 0, 1, -1};
    public static int[] dy = {-1, 1, 0, 0};
    // 맵의 크기 = -5 ~ 5까지이므로 11x11
    public static boolean[][][][] visit = new boolean[11][11][11][11];
    
    public int solution(String dirs) {
        int answer = 0;
        
        /* x,y = 캐릭터가 이동하기 전 위치, nextX, nextY = 캐릭터가 이동한 후 위치 */
        int x = 0;
        int y = 0;
        // 문제의 범위는 -5~5이고, 배열의크기는0~10이므로 시작 위치를 +5로 잡아준다.
        int nextX = 5;
        int nextY = 5;
        
        int index = 0;
        
        for(int i=0; i<dirs.length(); i++){
            // 캐릭터의 현재 위치 저장
            x = nextX;
            y = nextY;
            if(dirs.charAt(i) == 'U') 
                index = 0;
            else if(dirs.charAt(i) == 'D')  
                index = 1;
            else if(dirs.charAt(i) == 'R')  
                index = 2;
            else if(dirs.charAt(i) == 'L')  
                index = 3;
            
            // U, D, R, L에 맞는 캐릭터 위치 이동
            nextX += dx[index];
            nextY += dy[index];
            
            // 이전에 움직인 범위에 의해 캐릭터의 위치가 지도를 벗어났을 경우
            if(nextX < 0 || nextY < 0 || nextX > 10 || nextY > 10){
                // 다시 캐릭터를 전의 위치로 이동
                nextX -= dx[index];
                nextY -= dy[index];
                continue;
            }
            
            // 캐릭터가 처음 걸어본 길일경우
            if(!visit[x][y][nextX][nextY] && !visit[nextX][nextY][x][y]){
                // 걸어온 길 체크(점이 아닌 길이기 때문에 양방향으로 체크한다.)
                visit[x][y][nextX][nextY] = true;
                visit[nextX][nextY][x][y] = true;
                answer ++;
            }
        }
        return answer;
    }
}

풀이

U: 위쪽으로 한칸

D: 아래쪽으로 한칸

R: 오른쪽으로 한칸

L: 왼쪽으로 한칸

https://blog.naver.com/PostView.nhn?blogId=jaeyoon_95&logNo=221790432130&categoryNo=74&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView

 

문제에서 주어진 그대로 해결하면 된다.

먼저 캐릭터가 움직일수 있는 ↑(y+1) , ↓(y-1) , →(x+1) , ←(x-1) 방향에 맞게 dx, dy 배열을 선언해주고,

맵은 -5부터 5까지이지만 배열의 인덱스는 0부터하므로, +5씩 더해서 0~10까지 맵을 설정할

4차원 boolean 배열을 선언해 주었다.[현재위치(2차원), 이동위치(2차원) 체크를 해야한다.]

    public static int[] dx = {0, 0, 1, -1};
    public static int[] dy = {-1, 1, 0, 0};
    // 맵의 크기 = -5 ~ 5까지이므로 11x11
    public static boolean[][][][] visit = new boolean[11][11][11][11];

 

그 후 캐릭터의 현재 위치를 저장할 변수(x,y) 와 이동 후 위치를 저장할 변수(nx, ny)을 선언한다.

이때 맵을 우측으로 5칸씩 이동했으므로, 이동후의 변수 초기값을 5로 설정한다.

이제 주어진 문자열의 각 문자를 기준으로 탐색을 시작한다.

캐릭터의 현재 위치는 (5,5) 이므로 x, y 값을 설정한다.

            x = nx;
            y = ny;

 

그 후 각 문자가 U, D, R, L에 따라 위에서 설정한 dx, dy의 인덱스에 맞게 0, 1, 2, 3로 저장하고, 캐릭터의 위치를 이동시킨다.

 

만약 캐릭터의 이동 위치가 맵을 벗어났을 경우(맵의 범위는 0 ~ 10까지)

이전에 이동시킨 캐릭터를 원위치 시킨다.

 

다음으로 캐릭터가 처음 왔던 길인경우, 이전의 길 + 현재의 길 모두 체크표시를 한다.

 

 

 

* *

맵의 크기는 10x10이고, 처음에는 아무 생각없이 로봇이 이동하는 위치를 2차원 boolean 배열에 체크해주고,

만약 체크되어 있는 길일경우 길이를 줄이는 방식으로 해결하려고 헀는데,,

당연히 배열에는 마이너스 인덱스가 들어갈 수 없다.

이 문제를 풀면서 좌표평면과 2차원행렬과의 x, y축 좌표값이 조금 헷갈렸다.

2차원 배열의 이동 전 + 이동 후 체크를 4차원 배열로 체크해 줄 수 있고, 주어진 문제의 평면을 약간 이동시켜서 풀 수 있는법을 배웠다.