[프로그래머스] 방문 길이 (Lv.2)

✴️ 문제

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

 

 

✴️ 문제 풀이

 

문제가 굉장히 길지만 문제 풀이에 대한 설명일 뿐 조건은 간단했다.

주어진 방향대로 움직이면서 내가 처음 가본 길의 갯수를 구해라!

 

우선 U, D, L, R을 (x, y) 배열로 생각해 dx와 dy 배열을 선언해준다.

그리고 방문 여부를 나타낼 visited 2차원 배열도 선언해준다.

그림에서 확인할 수 있듯이 x, y 값이 모두 -5에서 5까지의 값을 갖기 때문에 (0, 0)은 정가운데 지점이다.

2차원 배열의 위치가 -5부터 5까지 지정해주기 어려우니 (0, 0)부터 (10, 10)값을 가진다고 가정하고 풀이를 진행했다.

즉, 11개의 열과 행을 가지는 좌표에 대해서 (5, 5) 지점이 우리가 생각하는 (0, 0)지점이다.

이 부분이 좀 헷갈릴 수 있다.

 

이제 주어진 값에 따라 이동을 시켜준다.이동했을 때의 위치가 좌표를 넘어선다면 이동하지 않는다.그렇지 않다면? 방문 여부를 확인해주고 첫방문이라면 answer++

 

이 문제에서 중요한 점은 처음 가보는 길을 어떻게 처리할 것인지였다.

길에는 출발점과 도착점이 존재하는데 둘다 2차원 배열의 값이기 때문에 좌표값으로 해주려면 4개의 값이 필요한 상황,,

하지만 각각의 좌표를 하나의 점으로 생각한다면?

(0,0)과 (0,1)을 각각 0번째, 1번째 지점으로 생각한다면?

좌표는 (0, 0)부터 (10, 10)까지 121개의 지점으로 생각할 수 있다.

 

이를 처리하기 위해서 각 좌표에 대해서 지점을 구해주는 식은 아래와 같다.

int start = x * 11 + y;
int end   = nx * 11 + ny;

 

이때 0 -> 1 을 지나가는 길과 1 -> 0을 지나가는 길을 같으니 양방향으로 처리해줘야한다.

if(!visited[start][end]){
	visited[start][end] = true;
	visited[end][start] = true;
	answer++;
}

 

✴️ 전체 코드 (Java)

import java.util.*;

class Solution {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited;
    
    public int solution(String dirs) {
        int answer = 0;
        int x = 5, y = 5;
        visited = new boolean[121][121];
        
        for(int i = 0; i < dirs.length(); i++){
            char cmd = dirs.charAt(i);
            int nx = 0, ny = 0;
            switch(cmd){
                case 'U':
                    nx = x + dx[0];
                    ny = y + dy[0];
                    break;
                case 'D':
                    nx = x + dx[1];
                    ny = y + dy[1];
                    break;
                case 'L':
                    nx = x + dx[2];
                    ny = y + dy[2];
                    break;
                case 'R':
                    nx = x + dx[3];
                    ny = y + dy[3];
                    break;
            }
            
            if(nx < 0 || nx > 10 || ny < 0 || ny > 10) continue;

            // 방문 처리
            int start = x * 11 + y;
            int end   = nx * 11 + ny;
            if(!visited[start][end]){
                visited[start][end] = true;
                visited[end][start] = true;
                answer++;
            }
            x = nx;
            y = ny;     
        }
        
        return answer;
    }
}