프로그래머스 - 방문길이

프로그래머스 - 방문길이

import java.util.*;

class Solution {
    
    List<String> list = new ArrayList<>();
    
    public int solution(String dirs) {
        int answer = 0;
        
        String[] split = dirs.split("");
        
        int x=5,y=5;
        
        for (int i=0;i<split.length;i++) {
            String order = split[i];
            
            int nx = x;
            int ny = y;
            
            if (order.equals("U")) {
                ny+=1;
            } else if (order.equals("D")) {
                ny-=1;
            } else if (order.equals("L")) {
                nx-=1;
            } else {
                nx+=1;
            }
            
            if (nx <0 || nx>=11 || ny<0 || ny>=11 ) {
                continue;
            }
            
            String kc = x+""+y;
            String kn = nx+""+ny;
            
            String path1 = kc+kn;
            String path2 = kn+kc;
        
            if (!list.contains(path1)) {
                list.add(path1);
                list.add(path2);
                answer++;   
            } 
            
            x = nx;
            y = ny;
            
        }
        
        return answer;
        
    }
}

처음에는 지나온 길 체크를 제대로 못해서 시간이 걸렸다. 이 문제의 핵심은 결국 지나온 길을 어떻게 체크를 할 것인가이다.
처음에는 바보같이 boolean[][] 배열로 풀어보려 했지만 제대로 나오지 않았다. 이유는 간단한데 예를 들어 (2,1) -> (1,1) -> (2,1)로 갔을 경우 boolean으로 하게 되면 첫 경로는 체크가 되지만 이후 2번째 경로에서 막히게 된다.
그러므로 지나온 길을 체크하는데에 있어서 애매한 부분이 있어 String으로 처리하였는데 kc의 경우 현재 나의 위치를 String으로 저장하였고 kn의 경우는 내가 다음 번 갈 길을 String으로 저장하였는데 이 값을 list에 넣어 지나온 길을 체크하였다. 위의 경우 "2111"과 "1121"을 저장해 주어서 왔던 길을 체크 해 주었다.
위 코드에서 list대신 set을 사용하고 answer 부분을 size()로 체크하면 더 좋을 것 같다.

출처: 프로그래머스 알고리즘;