[프로그래머스]Lv2.파헤치기 자바(Java) 방문 길이

우선 문제의 내용을 이해해 보자.
문제를 보면, (문제참고)

0,0이라는 위치에서

-5~5로 각각 구성된 x와 y filed에서
이동 명령표에 따라 이동하며(U,D,L,R)
방문하는 '선'이 카운팅되는 것을 알 있다.

위를 통해 알 수 있는 것은 점이 아니기 때문에
boolean 배열을 통한 점 방문 표시를 사용할 수 없다는 점이었다.
그래서 위의 방식을 활용해 dfs로 구현하려던 초반의 계획은 불가능했다.

여기서 핵심 중 하나는 방문하는 선의 경우
한방향의 방문이 성립되면 양방향 방문으로 이루어져야 한다는 아이디어가 필요하다.

위의 말이 무슨 뜻인가 하면,
A->B는 B->A로 가는 카운팅 역시 이루어진 것으로 간주한다는 것이다.

즉, UDU라고 하면 이는 한번만 카운팅 된다. 올라갔다 내려왔다 올라가는 것은 동일하게 카운팅 되는 것.

이를 구현하기 위해, 현재의 위치(x,y) 이동하는 위치(nx, ny)를 두고 이를 조합해
set에 담아주는 형태로 구현을 했다.

방향을 담아 줄 d라는 int[][] 2차원 배열을 만들어주고, 각각의 명령어에 따라 매칭되게 만들었다.

이때 String으로 구현한 경우, 10초가 넘는 구현 속도를 보였어서,

추후, StringBuilder를 활용해 마지막에 String으로 변환해 주었다.

아래는 구현 코드이다.

아래의 코드는 VSC에서 프로그래머스.Lv2파헤치기
라는 패키지의
방문길이
라는 이름의 클래스로 만들어
main에서 실행하기 위해 solution을
static으로 지정해
구현한 예시이다.

package 프로그래머스.Lv2파헤치기;
import java.util.Set;
import java.util.HashSet;
public class 방문길이 {

    private static int solution(String dirs) {
       Set<String> set = new HashSet<>();//방향 저장자.
        int x = 0, y = 0;
        int[][] d = {{-1,0},{1,0},{0,-1},{0,1}};//방향지시자
        int idx = -1;
        for(char c : dirs.toCharArray()){
            if(c=='U') idx = 0;//상
            else if(c=='D') idx  = 1;//하
            else if(c=='L') idx = 2; //좌
            else if(c=='R') idx = 3; //우
        int nx = x + d[idx][0];//위치 조정
        int ny = y + d[idx][1];//위치 조정
            if(nx < -5 || ny < -5 || nx > 5 ||ny > 5){
                continue;
            }
            StringBuilder sb = new StringBuilder();
            sb.append(x).append(y).append(nx).append(ny);
            set.add(sb.toString());//현재위치에서 가는 방향의 값 저장
            sb = new StringBuilder();
            sb.append(nx).append(ny).append(x).append(y);
            set.add(sb.toString());//역방향도 카운팅 한 것이기에 값 저장
            x = nx;
            y = ny; //현재 위치 갱신
        }
        return set.size()/2;//양방향을 넣었기 때문에 절반만
    }
    public static void main(String[] args) {
        System.out.println(solution("LULLLLLLU"));
    }
}