방문 길이

작성일: 2024-11-11

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

접근 방식

boolean 자료구조를 이용해, 방문처리를 하고, true 값만 리턴했다.

잘못된 접근

import java.util.*;
import java.awt.*;

class Solution {
    class Pair{
        int x;
        int y;
        Pair(int x, int y){
            this.x=x;
            this.y=y;
        }
    }

    public int solution(String dirs) {
        int answer = 0;
        boolean[][] visited = new boolean[11][11];
        Set<int[]> set = new HashSet<>();
        Pair p = new Pair(5, 5);
        for(char d:dirs.toCharArray()){
            // 위로
            if(d=='U'){
                if(p.x-1<0) continue;
                p.x--;
                if(!visited[p.x][p.y]) answer++;
                visited[p.x][p.y]=true;
            }
            // 아래로
            else if(d=='D'){
                if(p.x+1>10) continue;
                p.x++;
                if(!visited[p.x][p.y]) answer++;
                visited[p.x][p.y]=true;
            }
            // 오른쪽
            else if(d=='R'){
                if(p.y+1>10) continue;
                p.y++;
                if(!visited[p.x][p.y]) answer++;
                visited[p.x][p.y]=true;
            }
            // 왼쪽
            else{
                if(p.y-1<0) continue;
                p.y--;
                if(!visited[p.x][p.y]) answer++;
                visited[p.x][p.y]=true;
            }
        }

        return answer;
    }
}

하지만 문제가 발생했다.

예를 들어서 (0, 0)에 도착할 수 있는 방법은 4가지가 존재한다. (위, 아래, 왼쪽, 오른쪽)

하지만 좌표로 방문처리를 할 경우, 방법을 따지지 않고 목표에 갔었다면 방문으로 처리하여 카운트를 하지 않는 문제가 발생했다.

잘못 된 접근2

그래서 현재 좌표와 이동 후 좌표를 저장했다.

이 역시도 문제가 발생했다. 바로 배열 객체로 저장할 경우 값이 같더라도 다른 객체로 인식하여 이미 이동했던 경로더라도 중복하여 값이 저장됐다.

import java.util.*;
import java.awt.*;

class Solution {
    class Pair{
        int x;
        int y;
        Pair(int x, int y){
            this.x=x;
            this.y=y;
        }
    }

    public int solution(String dirs) {
        int answer = 0;
        boolean[][] visited = new boolean[11][11];
        Set<int[]> set = new HashSet<>();
        Pair p = new Pair(5, 5);
        for(char d:dirs.toCharArray()){
            // 위로
            if(d=='U'){
                if(p.x-1<0) continue;
                set.add(new int[] {p.x, p.y, p.x-1, p.y});
                p.x--;

            }
            // 아래로
            else if(d=='D'){
                if(p.x+1>10) continue;
                set.add(new int[] {p.x, p.y, p.x+1, p.y});
                p.x++;
            }
            // 오른쪽
            else if(d=='R'){
                if(p.y+1>10) continue;
                set.add(new int[] {p.x, p.y, p.x, p.y+1});
                p.y++;
            }
            // 왼쪽
            else{
                if(p.y-1<0) continue;
                set.add(new int[] {p.x, p.y, p.x, p.y-1});
                p.y--;
            }
        }

        return set.size();
    }
}

잘 된 접근

정답은 String에 있었다. 현재 좌표와 이동 후 좌표를 String 객체로 변환하여 저장한다. 반대의 경우 (목표->현재) 에도 방문으로 처리해야 하기 때문에, 반대 경우의 좌표도 변환하여 저장한다.

이렇게 하면 목표 좌표로의 이동이 Set 자료구조에 잘 저장된다. 이를 통해 중복 방문을 방지 할 수 있다.

최종 값 리턴에는, 왕복 방문으로 Set에 값을 넣었기 때문에 /2를 하여 값을 리턴한다.

결과

소스 코드

import java.util.*;

class Solution {
    class Pair {
        int x, y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int solution(String dirs) {
        int answer = 0;
        Set<String> set = new HashSet<>();
        Pair p = new Pair(5, 5);

        for (char d : dirs.toCharArray()) {
            int nx = p.x, ny = p.y;

            if (d == 'U') nx--;
            else if (d == 'D') nx++;
            else if (d == 'R') ny++;
            else if (d == 'L') ny--;

            // 범위 확인
            if (nx < 0 || nx > 10 || ny < 0 || ny > 10) continue;

            // 경로를 양방향으로 저장
            String path1 = p.x + "," + p.y + "-" + nx + "," + ny;
            String path2 = nx + "," + ny + "-" + p.x + "," + p.y;

            set.add(path1);
            set.add(path2);

            p.x = nx;
            p.y = ny;
        }

        return set.size() / 2; // 양방향 저장이기에 /2
    }
}

다른 접근 방식

없음.

알게 된 점

없음.