프로그래머스: 방문 길이(JAVA)

 

게임 캐릭터를 상하좌우로 움직이면서 **지나간 '서로 다른 길의 수'**를 구하는 문제입니다. 단, 한 번 지나간 길은 다시 지나가도 새로운 길로 취급하지 않습니다.

---

문제 설명

• 초기 위치: (0, 0)
• 명령어:
  • U: 위로 한 칸
  • D: 아래로 한 칸
  • L: 왼쪽으로 한 칸
  • R: 오른쪽으로 한 칸
• 좌표 제한: x, y ∈ [-5, 5]
• 중복 경로: 같은 길은 한 번만 센다 (양방향 포함)

---

풀이

• Set<String>을 사용해서 중복되지 않는 경로만 저장한다.
• 경로를 "x1,y1,x2,y2" 형식으로 저장하며, 양방향 모두 저장한다.
  • 예: (0,0) → (0,1) 와 (0,1) → (0,0)은 같은 경로로 간주
• 경계 밖으로 이동하려는 명령은 무시한다.
• 마지막에 Set 크기를 2로 나눠서 실제 경로 개수를 구한다.

---

JAVA

import java.util.*;

class Solution {
    public int solution(String dirs) {
        Set<String> map = new HashSet<>();

        int x = 0;
        int y = 0;

        for (int i = 0; i < dirs.length(); i++) {
            int nx = x;
            int ny = y;

            switch (dirs.charAt(i)) {
                case 'U': ny++; break;
                case 'D': ny--; break;
                case 'L': nx--; break; 
                case 'R': nx++; break; 
            }

            // 좌표 제한 벗어나면 무시
            if (nx > 5 || nx < -5 || ny > 5 || ny < -5) continue;

            // 경로 양방향으로 저장
            map.add(x + "," + y + "," + nx + "," + ny);
            map.add(nx + "," + ny + "," + x + "," + y);

            x = nx;
            y = ny;
        }

        return map.size() / 2;
    }
}

 

 

• 양방향 저장 대신, 항상 (작은 좌표 → 큰 좌표)로 경로를 정렬해서 저장하면 map.size() 그대로 정답이 됩니다.
• 예를 들어 아래처럼 정렬

String path = Math.min(x, nx) + "," + Math.min(y, ny) + "," + Math.max(x, nx) + "," + Math.max(y, ny);
map.add(path);