문제링크

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

구현방법

처음에는 BFS로 풀면되겠다 생각했었는데 이경우 가장 큰 문제점이 발생했다.

경주로가 완성됬을 때 값을 계속 갱신해야했는데 2차원 배열에서는 값을 저장할 때 -> 초반에 값이 커졌다가 나중에 최소 값보다 값이 작아지는 경우 값을 갱신이 불가능하다는 점이있었다.

그래서 3차원 배열을 통해서 방향까지 포함해서 진행할 경우 -> 값이 제대로 저장안되는 문제를 해결할 수 있었습니다.

-> 3차원으로 풀경우가 쉽게 풀리는 것을 보고 3차원 배열도 고려를 해봐야겠다고 생각이 든다.

알고리즘

BFS + DP

CODE

import java.util.*;


class Solution {

    int[][] maps;
    int rows;
    int cols;

    //좌,상,우,하
    int dx[] = {0, -1, 0, 1};
    int dy[] = {-1, 0, 1, 0};


    //비용체크용
    int cost = Integer.MAX_VALUE;

    boolean visited[][][];


    public int solution(int[][] board) {
        maps = board;
        rows = maps.length;
        cols = maps[0].length;
        visited = new boolean[rows][cols][4];


        BFS(0, 0);

        return cost;
    }

    public void BFS(int row, int col) {
        Queue<road> queue = new LinkedList<>();
        //방향은 현재 아직 정해지지않았기때문에 0으로 지정
        //좌,상,우,하 로 진행해보자

        queue.offer(new road(row, col, 5,0));


        while (!queue.isEmpty()) {
            road cur = queue.poll();

            //목적지 도달시
            if (cur.row == rows - 1 && cur.col == cols - 1) {
                cost = Math.min(cost, cur.costs);
            }


            for (int idx = 0; idx < 4; idx++) {
                int nxt_row = cur.row + dx[idx];
                int nxt_col = cur.col + dy[idx];



                //범위를 벗어나는경우는 제외
                if (nxt_row < 0 || nxt_col < 0 || nxt_row >= rows || nxt_col >= cols) {
                    continue;
                }

                //벽일경우만 pass
                if (maps[nxt_row][nxt_col] == 1) {
                    continue;
                }

                int nxt_price = cur.costs;

                if (cur.direction == 5 || cur.direction == idx) {
                    nxt_price +=100;
                }else {
                    nxt_price +=600;
                }

                if(!visited[nxt_row][nxt_col][idx] || maps[nxt_row][nxt_col] >= nxt_price){
                    queue.offer(new road(nxt_row,nxt_col,idx,nxt_price));
                    visited[nxt_row][nxt_col][idx] = true;
                    maps[nxt_row][nxt_col] = nxt_price;
                }
            }
        }

    }


    public class road {
        int row;
        int col;

        //전체 값 체크용도
        int costs=0;

        //방향 체크 (코너가 만들어지는지 체크하기 위해서)
        int direction;


        public road(int row, int col, int direction,int costs) {
            this.row = row;
            this.col = col;
            this.direction = direction;
            this.costs = costs;
        }
    }
}

실패한 코드 (2차원을 풀 경우 체크가 안됨.)

import java.util.*;

class Solution {
    private static int n;
    private static int[][] map;
    private static boolean[][] visit;

    private static int[] dx = {-1, 0, 1, 0}; //상우하좌
    private static int[] dy = {0, 1, 0 ,-1};

    private static int cost = Integer.MAX_VALUE;

    public int solution(int[][] board) {
        int answer = 0;

        n = board.length;

        map = board;
        visit = new boolean[n][n];

        bfs(0,0,5,0);

        answer = cost;

        return answer;
    }

    private static void bfs(int x, int y, int dir, int price) {

        Queue<Road> q = new LinkedList();
        q.add(new Road(x,y,dir,price));
        visit[x][y] = true;

        while (!q.isEmpty()) {
            Road cur = q.poll();

            //목적지 도달시
            if (cur.row == rows - 1 && cur.col == cols - 1) {
                cost = Math.min(cost, cur.costs);
            }


            for (int idx = 0; idx < 4; idx++) {
                int nxt_row = cur.row + dx[idx];
                int nxt_col = cur.col + dy[idx];
                
                 int nxt_price = cur.costs;

                //범위를 벗어나는경우는 제외
                if (nxt_row < 0 || nxt_col < 0 || nxt_row >= rows || nxt_col >= cols) {
                    continue;
                }
                
                    //벽일경우 pass
                if (maps[nxt_row][nxt_col] == 1) {
                    continue;
                }
                
                if (cur.direction == 5 || cur.direction == idx) {
                    nxt_price +=100;
                }else {
                    nxt_price +=600;
                }

                if(!visited[nxt_row][nxt_col] || maps[nxt_row][nxt_col] >= nxt_price){
                    queue.offer(new road(nxt_row,nxt_col,idx,nxt_price));
                    visited[nxt_row][nxt_col] = true;
                    maps[nxt_row][nxt_col] = nxt_price;
                }

            }
        }

    }

}

    public class road {
        int row;
        int col;

        //전체 값 체크용도
        int costs=0;

        //방향 체크 (코너가 만들어지는지 체크하기 위해서)
        int direction;


        public road(int row, int col, int direction,int costs) {
            this.row = row;
            this.col = col;
            this.direction = direction;
            this.costs = costs;
        }
    }
}