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

https://school.programmers.co.kr/learn/courses/30/lessons/49994
이 문제는 방문했던 경로를 다시 방문하는 경우에는 길이 값을 더해주지 않는 문제이다.

초반에는 이 문제를 풀 때, 각 좌표를 이중 배열의 index값으로 선언하고, 그 안에 hashset을 통해 방문한 방향만 넣어주었다. 하지만, 25점으로 모든 test case를 통과하지 못했었다. 다시 생각을 해 보니 한 길을 오른쪽으로 간 것과 왼쪽으로 간 것이 다른 것이 아니라 동일하다는 사실을 깨달았다.

위의 그림처럼 오른쪽으로 한 칸 이동한 경우와, 왼쪽으로 한 칸 이동한 경우는 같은 길을 지난 것이다. 그러므로 반대 방향도 고려 해 주어야 한다.

나는 현재 좌표에서의 이동 방향과, x,y를 각각 증가시키기 전 좌표에서의 이동 방향을 모두 고려해 주었다.

위 그림에서 (1,0)로 이동하는 경우에는 (1,0)에 왼쪽에서 오른쪽으로 이동했다고 표시하고, (0,0)에는 오른쪽에서 왼쪽으로 이동했다고 표시하여 더 이상 새로운 길이 아니라는 뜻으로 저장해 주었다.

import java.util.*;

class Solution {
    public int solution(String dirs) {
        //U : x그대로, y+1
        //D : x그대로, y-1
        //R : x+1, y그대로
        //L : x-1, y그대로
        //범위에서 벗어나면 그 명령어 무시
        //그 좌표에 저장할 때 어느 방향에서 왔는지도 같이 저장
        HashSet<String>[][] coor = new HashSet[11][11]; //좌표의 방향 저장할 hashset 타입 이중배열
        //coor[0][0]에는 0,0을 방문한 hashset이 들어가 있는 것
        //hashset안에 있으면 무시하고, 없으면 cnt 값 증가
        //반대방향도 고려해야됨
         for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                coor[i][j] = new HashSet<>();
            }
        }

        int cnt = 0;
        //5,5가 원점
        int x = 5;
        int y = 5;
        
        for(int i=0;i<dirs.length();i++){
            char dir = dirs.charAt(i);
            if(dir == 'U'){
                if(y>=0 && y<=10){
                    y = y + 1;
                      if(y>=0 && y<=10){
                          if(!coor[x][y].contains("U") && !coor[x][y-1].contains("D")){
                              coor[x][y].add("U");
                              coor[x][y-1].add("D");
                              cnt++;
                          }
                      }else{
                          y = y - 1; //조건에 맞지 않으면 더해준 것을 다시 빼 주어야 함
                      }
                }
            }else if(dir == 'D'){
                if(y>=0 && y<=10){
                    y = y - 1;
                    if(y>=0 && y<=10){
                        if(!coor[x][y+1].contains("U") && !coor[x][y].contains("D")){
                            coor[x][y+1].add("U");
                            coor[x][y].add("D");
                            cnt++;
                        }
                    }else{
                        y = y + 1;
                    }
                }
            }else if(dir == 'R'){
                if(x>=0 && x<=10){
                    x = x + 1;
                    if(x>=0 && x<=10){
                        if(!coor[x][y].contains("R") && !coor[x-1][y].contains("L")){
                            coor[x][y].add("R");
                            coor[x-1][y].add("L");
                            cnt++;
                        }
                    }else{
                        x = x - 1;
                    }
                }
            }else if(dir == 'L'){
                if(x>=0 && x<=10){
                    x = x - 1;
                      if(x>=0 && x<=10){
                          if(!coor[x+1][y].contains("R") && !coor[x][y].contains("L")){
                              coor[x+1][y].add("R");
                              coor[x][y].add("L");
                              cnt++;
                          }
                      }else{
                          x = x + 1;
                      }
                }
            }
        }
        return cnt;
    }
}