방문 길이

문제

게임 캐릭터가 좌표평면의 (0, 0) 위치에서 시작하여 U, D, R, L 방향으로 1칸씩 이동합니다. 좌표평면의 경계는 x, y 좌표 모두 -5부터 5까지입니다. 경계를 벗어나는 명령어는 무시되며 캐릭터는 이동하지 않습니다. 명령어가 주어졌을 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하는 프로그램을 작성하는 문제입니다.

• 입력: 명령어를 나타내는 문자열 dirs (길이 500 이하, 'U', 'D', 'R', 'L'로 구성)
• 출력: 처음 걸어본 길의 길이(정수)를 반환합니다.

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

풀이: 경로 관리와 HashSet의 활용

단순히 방문한 '점(좌표)'이 아니라 이동한 '경로(선분)'를 추적해야 하는 문제입니다. HashSet을 이용해 중복을 제거하며 처음 걸어본 길의 개수를 셉니다.

• 양방향 경로의 동일 취급 (핵심 로직): A 좌표에서 B 좌표로 이동한 길과, B 좌표에서 A 좌표로 이동한 길은 '같은 길'입니다. 따라서 Path 객체를 생성할 때 출발점과 도착점의 좌표 크기를 비교하여, 항상 더 작은 좌표가 출발점(sy, sx)이 되도록 정렬하여 저장해야 방향에 상관없이 동일한 경로로 취급할 수 있습니다.
• equals와 hashCode 오버라이딩: 직접 생성한 Path 클래스 객체를 HashSet에 넣을 경우, 기본적으로 메모리 주소를 비교하므로 내용이 같아도 다른 객체로 인식합니다. 내부 좌표값(sy, sx, ey, ex)이 같으면 동일한 객체로 판단하도록 equals와 hashCode 메서드를 반드시 오버라이딩해야 정상적으로 중복이 제거됩니다. 

코드

import java.util.*;

class Solution {
    public int solution(String dirs) {
        int y = 0;
        int x = 0;
        
        Set<Path> set = new HashSet<>();
        for (char c : dirs.toCharArray()) {
            int ny = y;
            int nx = x;
            if (c == 'U') {
                ny += 1;
            } else if (c == 'D') {
                ny -= 1;
            } else if (c == 'L') {
                nx -= 1;
            } else if (c == 'R') {
                nx += 1;
            }
            
            // x, y 모두 -5 미만 또는 5 초과일 경우 무시
            if (ny < -5 || ny > 5 || nx < -5 || nx > 5) continue;
            
            set.add(new Path(y, x, ny, nx));
            y = ny;
            x = nx;
        }
        
        return set.size();
    }
    
    class Path {
        int sy, sx, ey, ex;
        
        public Path(int y1, int x1, int y2, int x2) {
            // 항상 좌표값이 더 작은 쪽을 출발점(sy, sx)으로 고정하여 양방향을 동일하게 처리
            if (y1 < y2 || (y1 == y2 && x1 < x2)) {
                this.sy = y1;
                this.sx = x1;
                this.ey = y2;
                this.ex = x2;
            } else {
                this.sy = y2;
                this.sx = x2;
                this.ey = y1;
                this.ex = x1;
            }
        }
        
        // HashSet 중복 판별을 위한 오버라이딩
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Path path = (Path) o;
            return sy == path.sy && sx == path.sx && ey == path.ey && ex == path.ex;
        }

        @Override
        public int hashCode() {
            return Objects.hash(sy, sx, ey, ex);
        }
    }
}

알고리즘 분류

구현 (Implementation), 시뮬레이션 (Simulation), 해시를 사용한 집합 (Hash Set)