[프로그래머스][lv2] 방문길이 Java

문제 설명

게임 캐릭터를 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문제의 예시와 같습니다.

나만의 풀이(문제 해결하지 못함)

1. 각각 10의 길이를 갖는 2차원 배열을 만들고
2. 중앙에서 시작해야 하므로 arr[5][5]부터 시작
3. for iter문으로 String을 돌면서 단어가 수행해야 하는 로직을 arr에서 실행하는데, 만약 이동한 arr[][] 값의 인덱스가 0보다 작거나, 혹은 n보다 크거나 같다면 로직을 수행하지 않는다.
4. 한번 지나간 길은 1로 변환하고 만약 인덱스 값이 1이라면 cnt를 수행 x
5. arr[5][5]부터 시작하고 String에서 루프문을 돌면서 나오는 char 값이 처리되었을 때 그 인덱스 위치에 존재해야 하므로 x좌표와 y좌를 변경하는 로직을 구현한다.

ArrayBoundsIndex 에러가 발생 -> 생각해보면 인덱스가 0일 때 로직이 수행되선 안되고, 인덱스가 n-1일 때 로직이 수행되어선 안된다. 왜냐하면 0일 때 감소하면 -1이 되어버리고, n-1일 때 증가하면 n이 되어버리기 때문이다.

조건에서 인덱스가 0보다 크거나 n-1보다 작거나로 설정을 해줬는데 이게 x 값이 이동할 때의 경우에는 x 값에만 위 조건을 넣어야 한다 왜냐면 y 값이 0이고 x 값이 4일 때 x 값을 하나 감소시켜줘야 하는 상황이 발생했는데, y 값이 0이기 때문에 로직을 수행하지 않아버린다. 그래서 cnt도 증가하지 않고 올바른 값이 출력되지 않는다.

이 문제는 한번 지난 경로는 cnt 하지 않는 문제인데, 나는 좌표를 중점으로 문제를 해석해서 문제가 해결되지 않았다. 하나의 좌표는 동서남북으로 이동할 수 있기 때문에 가질 수 있는 횟수는 4개가 된다. 하지만 내 방식은 하나의 좌표는 하나의 cnt만 가질 수 있는 구조이다.

즉, 방향을 나타내는 인덱스가 필요하다는 것이다. 그래서 3차원 배열을 사용해야 한다.

 

[나의 문제 풀이]

package programmers.lv2;

import java.util.Scanner;

public class VisitLength {
    public int solution(String dirs){
        int answer = 0;

        int[][] arr = new int[11][11];

        int x = 5, y = 5;
        int cnt = 0;
        for(char t : dirs.toCharArray()){
                if(t == 'U'){
                    if(x > 0 && x < 10){
                        x--;
                        if(arr[x][y] != 1){
                            arr[x][y] = 1;
                            cnt++;
                        }
                    }
                }else if(t == 'L'){
                    if(y > 0 && y < 10){
                        y--;
                        if(arr[x][y] != 1){
                            arr[x][y] = 1;
                            cnt++;
                        }
                    }
                }else if(t == 'R') {
                    if(y > 0 && y < 10){
                        y++;
                        if(arr[x][y] != 1){
                            arr[x][y] = 1;
                            cnt++;
                        }
                    }
                }else{
                    if(x > 0 && x < 10){
                        x++;
                        if(arr[x][y] != 1){
                            arr[x][y] = 1;
                            cnt++;
                        }
                    }
                }
            System.out.println("t = "+ t + " x = " + x + ' ' + " y =" + y + " cnt =" + cnt);

        }

        answer = cnt;


        return answer;
    }

    public static void main(String[] args) {
        VisitLength T = new VisitLength();
        Scanner in = new Scanner(System.in);

        String dirs = in.next();


        System.out.println(T.solution(dirs));
    }
}

 

다른 사람의 풀이 방법

3차원 배열을 통해 방향을 나타내야 하므로

boolean visit[][][] = new boolean[11][11][4];

위와 같이 선언해준다. 맨 마지막 인덱스 4는 방향을 의미하는 인덱스이다.(동서남북)

이동했을 때 인덱스 값이 0보다 작거나 n보다 크거나 같다면 continue 해줘야한다.

if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

마지막으로 내가 이동하려는 방향과 내가 이동했을 때 그 이전으로 이동하는 방향을 true로 설정해줘야 한다. 만약 내가 이동하려는 방향이 이미 한번 지나온 방향이라면 answer 값이 증가하면 안된다.

if(!visit[nx][ny][d]){ //내가 이동하려는 방향이 true가 아닐 때만 로직을 수행한다 왜냐하면 이동하려는 방향이 true가 아니라는 의미는 한번도 이동한적이 없다는 의미이기 때문이다.
	visit[nx][ny][d] = true; //이동 했으므로 true 값을 넣어준다.
	d = (d%2 == 0) ? 2-d : 4-d; // d 값을 변경해준다 내가 이동한 방향과 이동한 좌표에서 그 이전의 자표로 이동하는 방향을 구분하기 위함이다.
	visit[x][y][d] = true;
	answer++;	
}
x = nx;
y = ny;

[전체코드]

import java.util.Scanner;

public class VisitLengthOther {
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, -1, 0, 1};
    public int solution(String dirs){
        int answer = 0;

        int x = 5, y = 5;
        boolean[][][] visit = new boolean[11][11][4];

        for(char t : dirs.toCharArray()){
            int d = 0;
            if(t=='U') d = 0;
            else if(t=='L') d = 1;
            else if(t=='D') d = 2;
            else d = 3;

            int nx = x + dx[d]; // 이동이 적용된 인덱스 위치 값
            int ny = y + dy[d];

            if(nx < 0 || ny < 0 || nx >= 11 || ny >= 11) continue;
            if(!visit[nx][ny][d]){
                visit[nx][ny][d] = true;
                d = (d%2==0) ? 2-d : 4-d;
                visit[x][y][d] = true;
                answer++;
            }
            x = nx;
            y = ny;
        }

        return answer;
    }
}