[프로그래머스-java] Lv.3 경주로 건설

알고리즘 : BFS + DP

좌표에서 이동할 수 있는 4가지 방향에 대하여 저장하는 배열을 선언하여 DP+BFS를 진행.

---

문제 설명

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

프로그래머스

 

---

😁내 풀이

 

처음에는 이전의 방향성을 유지해서, 최선의 선택을 내리도록 하게 알고리즘을 구상했다.
하지만 배열의 사이즈가 크지 않고, 4가지 방향성에 대해서 탐색을 진행해도 지장이 없을 것 같아서
좌표평면에 위치에 4가지 방향의 cost를 담는 배열을 선언해서 저장한 후 최종 위치의 4가지 방향값 중

최솟값을 return하게 작성했다.

 

나름 가독성이 괜찮지 않나?

 

✈️필요한 정보

기존의 BFS문제들과 다르게 이 문제에서는 따로 class로 선언하여 원하는 정보를 저장하는 객체를 큐에 넣어야했다.
x,y좌표 / 방향 / 해당 좌표까지 오기까지 방향성에 따른 cost
이 4가지 정보를 담고 있는 Loc class를 선언하여 사용했다.

 

🪟몇가지 고려해야 할 상황

1. 대표적인 BFS 케이스 처럼 움직인 이후 좌표가 범위를 벗어나는 지 확인
2. 움직일 수 있는 위치인지 확인

• 벽으로 막혀 있는지, 출발 지점인지

3. Cost 계산

• 방향성이 이전과 같다면 +100
• 다르다면 코너돌기 +500 이동 +100 = 총 600 더하기
• ( 이 부분에서 500만 더해줘서 정답이 안나오길래 한참 해맸다 ㅜㅜ )
• 처음 시작점에서 시작하는 경우 무조건 100을 더하게 설정하였다.( 이 부분에서도 문제였음 )
• 제자리로 되돌아 오는 경우
  • 아래 그림처럼 노란색 형광펜 경로를 따라 도착한 B에서 BFS를 진행하면 다시 A 방향으로 돌아간다.
  • 여기서 A 방향으로 중복되어 경로를 갱신하는 부분을 생각해, A에서 B로 진행한 방향 - B에서 A로 진행한 방향을 뺏을 때 2가 나오면, 즉 서로 반대 방향을 의미하므로 단순하게 100으로 계산하였다.
  • 이렇게 계산해도 되는 이유는 어처피 최종 도착지 기준으로는 이러한 반대 방향성으로 계산 되는 일이 없기 때문이다.

 

 

 

import java.util.*;
// 좌표, 방향, 현재까지 cost 
class Loc {
    int x;
    int y;
    int cost;
    int dir;

    public Loc (int x,int y,int cost,int dir){
        this.x = x;
        this.y = y;
        this.cost = cost;
        this.dir = dir ;
    }
}
class Solution {
    private static int N;
    private static int[][][] dist;
    // 방향 
    private static int[] dx = {-1,0,1,0};
    private static int[] dy = {0,1,0,-1};
    // 움직임이 좌표를 벗어나는 지 확인 
    private static boolean isOut(int nx,int ny){
        return (nx < 0 || nx >=N || ny < 0 || ny >= N);
    }

    // 방향성에 따른 cost 계산 
    private static int calCost(int prevDir,int currentDir,int cost){
        if ( prevDir == currentDir || Math.abs(prevDir - currentDir) == 2){
            return cost+ 100;
        }
        else return cost + 600;
    }
    public int solution(int[][] board) {
        // 보드의 크기 저장 및 초기화
        N = board.length;
        dist = new int[N+1][N+1][4];
        ArrayDeque<Loc> q = new ArrayDeque<>();

        // BFS 수행하면서 이전 방향 정보 바탕으로 갱신 
        q.offer(new Loc(0,0,0,-1));
        while (!q.isEmpty()){
            Loc cur = q.poll();

            for (int dir = 0; dir < 4; dir++){
                int nx = cur.x + dx[dir];
                int ny = cur.y + dy[dir];
                if(isOut(nx,ny)) continue;
                if (board[nx][ny] != 0 || (nx == 0 && ny == 0)) continue;

                int newCost = calCost(cur.dir,dir,cur.cost);

                if (dist[nx][ny][dir] ==0 || dist[nx][ny][dir] > newCost){
                    if (cur.x == 0 && cur.y == 0 ){
                        newCost = 100;
                    }

                    dist[nx][ny][dir] = newCost;
                    q.offer(new Loc(nx,ny,newCost,dir));
                } 
            }
        }
        int minum = Integer.MAX_VALUE;
        for (int i: dist[N-1][N-1]){
            if (i !=0) minum = Math.min(minum,i);
        }
        return minum;
    }
}