프로그래머스 - 경주로 건설 문제 (자바)

programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

일반적인 경로 찾는 bfs 문제

두가지 정도 고려사항이 추가됩니다. 

첫번째로 방문 처리가 없이 cost 비교로 작은 값으로 셋팅해야합니다.

두번째로 방향성을 고려해야하기 때문에 방향을 포함하는 객체를 이용해야합니다.

 

ps

시작 지점은 방향성을 고려하지 않아도 됩니다.

(저 같은 경우 -1로 처리 하였습니다.) 

import java.util.*;

class Road {
    int x;
    int y;
    int cost;
    int dir;

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

// 프로그래머스 경주로 건설 문제
class Solution {
    // 상하좌우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] map;
    static int answer = Integer.MAX_VALUE;

    public int solution(int[][] board) {
        map = board;
        bfs(new Road(0, 0, 0, -1));
        return answer;
    }

    void bfs(Road road){
        Queue<Road> queue = new LinkedList<>();
        queue.add(road);
        map[road.x][road.y] = 1; // 출발지점 벽으로 처리

        while (!queue.isEmpty()) {
            Road now = queue.poll();

            if(now.x == map.length - 1 && now.y == map[map.length - 1].length - 1) {
                answer = Math.min(answer, now.cost);
                continue;
            }

            for(int i = 0; i < 4; i++) {
                int nextX = now.x + dx[i];
                int nextY = now.y + dy[i];

                // 범위 밖인 경우
                if(nextX < 0 || nextX >= map.length || nextY < 0 || nextY >= map[map.length - 1].length) continue;

                // 벽인 경우
                if (map[nextX][nextY] == 1) continue;

                // 다음 지점 비용
                int nextCost = now.cost;
                if(now.dir == -1 || now.dir == i) {
                    nextCost += 100;
                }else {
                    nextCost += 600;
                }

                // 첫 방문 또는 이전 방문보다 비용이 적거나 같은 경우
                if(map[nextX][nextY] == 0 || map[nextX][nextY] >= nextCost) {
                    map[nextX][nextY] = nextCost;
                    queue.add(new Road(nextX, nextY, nextCost, i));
                }
            }
        }
    }
}