[카카오 인턴] 경주로 건설 - JAVA

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

프로그래머스

---

진짜... 진짜 어려웠다...

dp 가뜩이나 어려워하는데 여기에 bfs까지..?

bfs 변형이 진짜 생각하기 어려운 것 같다..🥲

그래도 어케... 해내야지...

버티는거야~ 버텨? 보는거야~ 일단 버티는거야~ 그럼 되는거야~

---

이 문제는 단순히 최단거리를 찾는 것이 아니라 최소비용을 찾아야 한다

따라서 bfs로 모든 경로를 탐색하면서 도착지에 도달하면 최소비용인지 확인하고 업데이트하면 된다

bfs를 사용해서 큐가 빌 때까지 반복하면 모든 경로를 탐색하니까 사용하면 된다!

 

근데? 여기서 중요한건 뭐다?

직진할 땐 100원인데 코너를 돌 땐 500원의 추가 비용이 발생한다

이 때 방향을 바꾸는 것만 500원이고 거기서 나아가려면 직진을 해야하니까 100원이 추가로 든다

따라서 코너를 돌 땐 총 600원의 비용이 발생하는 것이다

 

그리고 코너를 돈다는 것은 방향을 바꾼다는 것이기 때문에 현재 바라보고 있는 방향과 다음으로 나아가는 방향을 비교해서 코너를 도는지 여부를 판단해야 한다

 

그래서 dx, dy로 방향을 돌 때 반복문을 통해 도는데 그 반복문의 i 기준으로 방향을 생각하면 된다

 

요러고.. 풀었는데 마지막 테케가 통과가 안됐다...😰

찾아보니까 새로 추가 케이스가 들어온거 같은데 요걸 해결하려면 방향별 최소비용을 구해줘야 한다

이게 목적지까지 위에서 오는 것과 왼쪽에서 오는 것이 최소비용이 다를 수 있는데 단순 bfs로만 탐색을 하면 이 경우를 지나칠 수 있다고 한다

그래서 cost 배열을 3차원으로 선언해서 방향별 최소비용을 구하고 마지막에 방향별 최소비용 중 가장 작은 값을 리턴하면 된다!

 

솔직히.. 이거 코테에서 마주하면 풀 자신이 없다...

그래도 계속 연습해서 알고리즘 마스터 가보자고~!

 

 

자바 코드)

import java.util.*;

class Solution {
    static boolean[][] visit;
    static int answer; // 건설 비용
    static int n; // 배열 크기
    static int[][][] arr; //[dir][x][y]

    static class Point {
        int x, y, dir, cost;

        Point(int x, int y, int dir, int cost) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.cost = cost;
        }
    }

    public int solution(int[][] board) {
        // 직진 - 100, 코너 - 600
        // 코너를 돈다 = 방향을 바꾼다 => 현재 방향을 기억해야 한다
        answer = Integer.MAX_VALUE;
        n = board.length;
        arr = new int[4][n][n];
        for(int i=0;i<4;i++) {
            for(int x=0;x<n;x++) {
                for(int y=0;y<n;y++) {
                    arr[i][x][y] = Integer.MAX_VALUE;
                }
            }
        }
        visit = new boolean[n][n];

        bfs(0, 0, -1, 0, board); //(0,0)에서 출발, 초기 방향은 -1(출발)

        return answer;
    }

    private static void bfs(int x, int y, int dir, int cost, int[][] board) {
        int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
        int[] dy = {0, 0, -1, 1};

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

        while (!q.isEmpty()) {
            Point point = q.poll();
            int px = point.x;
            int py = point.y;
            int pdir = point.dir;
            int pcost = point.cost;

            if (px == n - 1 && py == n - 1) {
                answer = Math.min(answer, pcost);
            }

            for (int i = 0; i < 4; i++) {
                int nx = px + dx[i];
                int ny = py + dy[i];
                int ndir = i;
                int ncost = pcost;

                if(nx<0 || nx>=n || ny<0 || ny>=n || board[nx][ny]==1) {
                    continue;
                }

                if(pdir == -1) { // 출발하는 경우는 무조건 100
                    ncost += 100;
                } else if(pdir==ndir) { // 방향이 같다 - 직진
                    ncost += 100;
                } else { // 코너 돌기
                    ncost += 600;
                }

                if(!visit[nx][ny] || arr[ndir][nx][ny] >= ncost) {
                    visit[nx][ny] = true;
                    arr[ndir][nx][ny] = ncost;
                    q.add(new Point(nx, ny, ndir, ncost));
                }
            }
        }
    }
}

---

참고)

https://hidelookit.tistory.com/108

[프로그래머스] 2020 카카오 인턴십 - 경주로 건설 (Java)

https://minjheyy.tistory.com/145

[2020 카카오 인턴십] 경주로 건설