[JAVA] 프로그래머스 LEVEL2 방문 길이

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

프로그래머스

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

 

난이도: LEVEL2

알고리즘 유형: 구현

 

문제에서 좌표 범위는 -5 <= x <=  5 / -5 <= y <= 5 이다. 

 

나는 해당 좌표를 0 <= x <= 10 / 0 <= y <= 10 으로 바꿔서 풀었다. 

그럼 시작 좌표를 (5,5)로 잡고 풀면 된다. 

 

 

 

각 좌표를 고유한 숫자로 표현하기

좌표 정점 = x 좌표 * 11 + y 좌표 

그럼 (0,0) ~ (10,10) 까지 하나씩 0 ~ 120 고유의 좌표 정점으로 표현이 가능하다.

 

방문 표시 배열 

boolean [][] visited = new boolean [121][121]

 

정점 0 → 1 을 지나갔다면?

visited 배열에 visited[0][1] = true, visited[1][0] = true

0 → 1 / 1 → 0은 같은 길이다. 그래서 양방향으로 방문 표시를 해준다.  

 

만약 좌표평면 범위에 벗어났다면? 

해당 명령어는 무시해야 한다. 

그래서 벗어났는지를 판단하기 위해 검사 메소드를 만들었다. 

public static boolean validation(int nx, int ny){
    if(0 <= nx && 0 <= ny && nx <= 10 && ny <= 10) return true;
    return false;
}

 

만약 다음 이동 좌표의 검사가 false 반환이라면 이번 명령어를 무시하고 continue 한다. 

 

내가 실수했던 부분 

처음에 고유한 숫자 정점을 x * 10 + y로 만들어줬는데 

이렇게 만들면 (0, 10) (1, 0) 같은 숫자의 정점을 가지게 된다. 

 

0 * 10 + 10  → 10 

1 * 10 + 0   →  10

 

좌표 이동은 정상적으로 되지만 방문 표시에 오류가 생겨서 (70/100) 케이스만 통과되었었다. 

문제에 대한 아쉬운 부분 (개인적인 의견)
해당 문제는 0 → 1 / 1 → 0이 같은 길인지 명시해 줘야 한다고 생각한다. 

그에 따라 정답이 바뀔뿐더러 예시 테스트 케이스에는 좌표평면을 벗어나는 예시와 같은길에 대해서 같은 방향으로의 이동만 있지 양방향/단방향을 구분할 이동은

보여주지 않았다. 

근데 문제의 난이도가 그렇게 높지 않았고 방문 표시만 추가적으로 하면 되었기 때문에 

일부러 언급을 안 했을 가능성도 있다고 생각한다. 

정답 코드 

import java.util.*;
class Solution {
    static int [] arx = {-1,1,0,0}; // U -> D -> L -> R
    static int [] ary = {0,0,-1,1};
    public int solution(String dirs) {
        // 11 * 11 크기 
        boolean [][] visited = new boolean [121][121];
        int x = 5; int y = 5;
        int answer = 0;
        for(int i = 0; i < dirs.length(); i++){
            char cmd = dirs.charAt(i);
            int nx = 0; int ny = 0;
            switch (cmd){
                case 'U': {
                    nx = x + arx[0];
                    ny = y + ary[0];
                    break;
                }   
                case 'D': {
                    nx = x + arx[1];
                    ny = y + ary[1];
                    break;
                }   
                case 'L': {
                    nx = x + arx[2];
                    ny = y + ary[2];
                    break;
                }   
                case 'R': {
                    nx = x + arx[3];
                    ny = y + ary[3];
                    break;
                } 
            }
            if(!validation(nx, ny)) continue;
            int start = x * 11 + y;
            int end   = nx * 11 + ny;
            if(!visited[start][end]){
                visited[start][end] = true; // 양방향 
                visited[end][start] = true;
                answer++;
            }
            x = nx; y = ny;   
        }
        return answer;
    }
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx <= 10 && ny <= 10) return true;
        return false;
    }
}