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

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

프로그래머스

 

주어진 명령어가 주어졌을 때, 명령어대로 진행한 후에 처음 가본 길의 개수를 구하는 문제입니다.

 

처음가본 "길"에 집중하여 문제를 풀어야 합니다.

단지 노드를 방문했다고 해서 해당노드를 방문처리하고 끝내서는 안됩니다.

길에 초점을 맞춰서 (x1,y1) -> (x2, y2)의 노드로 진행하였다면

방문했던 길을 저장하는 HashSet에 (x1, y1, x2, y2)를 저장하는 방식으로 구현했습니다.

 

단,

(x1,y1) -> (x2, y2)과

(x2,y2) -> (x1, y1)

이 두가지 길은 결국 같은 길입니다. (길은 방향성이 없기 때문에)

 

따라서 한번 가본 길을 저장할 때 HashSet에 이 두개의 길을 다 저장한 후에 마지막 답을 구할때 /2를 해주는 식으로 구현하였습니다.

 

또, 주의할 점으로는 int[]의 equals 비교는 override를 할 수 없어서 감싸는 class를 또 만들어주어야하지만 List<Integer>는 equals비교가 요소(원소)비교로 이미 오버라이딩 되어 있기 때문에 간편하게 사용할 수 있습니다.

 

class Solution {

    static int[][] map = new int[11][11];
    static int[] dx = new int[]{-1, 1, 0, 0};
    static int[] dy = new int[]{0, 0, 1, -1};
    
    public int solution(String dirs) {
        int x = 5, y = 5;
        Set<List<Integer>> set = new HashSet<>();

        for(int i = 0; i<dirs.length(); i++){
            char c = dirs.charAt(i);
            int nx = 0, ny = 0;
            switch(c){
                case 'U':
                    nx = x + dx[0];
                    ny = y + dy[0];
                    break;
                case 'D':
                    nx = x + dx[1];
                    ny = y + dy[1];
                    break;
                case 'R':
                    nx = x + dx[2];
                    ny = y + dy[2];
                    break;
                case 'L':
                    nx = x + dx[3];
                    ny = y + dy[3];
                    break;
            }
            if(nx < 0 || ny < 0 || nx >= 11 || ny>= 11) continue;
            set.add(Arrays.asList(x, y, nx, ny));
            set.add(Arrays.asList(nx, ny, x, y));
            x = nx;
            y = ny;
        }
        return set.size() / 2;
    }
}