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

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

프로그래머스

 

접근 방식

(0,0)부터 (n-1, n-1)까지 도달한다고 할 때, 모든 경우의 수를 고려하는 것을 어떻게 할까? 가 첫번째 관문이였다.

백트래킹을 떠올렸으나, 25 x 25인 경우엔 시간초과가 날 것이기 때문에 제외했다.

 

boolean visited를 사용하여 코드를 짰지만, 당연히 하나의 최단경로만 탐색했다. 문제에서 원하는 것은 모든 경우의 수에서 최소 값이다.

 

따라서, int visited를 통해서 현재 값들을 배열에 저장해두고, 최소 비용이 갱신되는 경우에만 다음 칸으로 탐색이 가능하게 구현했다.

또한, 방향에 따라서 100, 600값이 달라지므로 현재 방향을 저장하는 값을 큐에 넣어서 다음 탐색 방향이 같은 경우 +100, 아닌경우 +600 이런식으로 구현했다. 

 

코드

import java.util.*;
class Solution {
    static int n;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int min_cost = Integer.MAX_VALUE;
    public int solution(int[][] board) {
        int answer = 0;
        n = board.length;
        
        bfs(0, board);
        bfs(1, board);
        
        return min_cost;
    }
    
    public void bfs(int direction, int[][] board) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0, direction, 0));
        
        int[][] visited = new int[n][n];
        visited[0][0] = 100;
        
        while(!q.isEmpty()) {
            Point cur = q.poll();
            int x = cur.x;
            int y = cur.y;
            int curDir = cur.dir;
            int cost = cur.cost;
            
            if (x == n - 1 && y == n - 1) {
                //System.out.println(cost);
                min_cost = Math.min(min_cost, cost);
                continue;
            }
            
            for(int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if (board[nx][ny] == 1) continue;
                
                int nextCost = 0;
                if (curDir == dir) nextCost = cost + 100;
                else nextCost = cost + 600;
                
                if (visited[nx][ny] == 0 || nextCost < visited[nx][ny]) {
                    visited[nx][ny] = nextCost;
                    q.add(new Point(nx, ny, dir, nextCost));
                }
            }
        }
    }
    
    public class Point {
        int x;
        int y;
        int dir;
        int cost;
        public Point(int x, int y, int dir, int cost) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.cost = cost;
        }
    }
}

 

후기

bfs만 보면 반사적으로 visited.. 이렇게 생각했는데 최소 cost를 계산하는 경우에는 int 배열을 통해 다음 탐색 지점을 찾도록 하자.