경주로 건설

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 경주로 건설

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

풀이 : 좌표정보, 방향, 비용의 정보를 가진 Car 클래스를 생성하여 Queue에 넣은 후 BFS 알고리즘을 사용하여 최저의 비용을 점검

import java.util.*;
class Solution {
    static class Car {
	int x, y, direction, cost;

	public Car(int x, int y, int direction, int cost) {
		this.x = x;
		this.y = y;
		this.direction = direction;
		this.cost = cost;
	}
}
    static int [][] map;
    static int [][] cost;
    static int min = Integer.MAX_VALUE;
    static LinkedList <Car> qu = new LinkedList<Car>();
    public int solution(int[][] board) {
        map = new int [board.length+2][board.length+2];
	cost = new int [board.length+2][board.length+2];
	for (int i = 0; i < map.length; i++) {
		for (int j = 0; j < map.length; j++) {
			if(i == 0 || j == 0 || i == map.length-1 || j == map.length-1) map[i][j] = 1;
			else map[i][j] = board[i-1][j-1];
		}
	}
	cost[1][1] = 100;
	if(map[1][2] == 0) {
		cost[1][2] = 100;
		qu.add(new Car(2, 1, 1, 100));
	}
	if(map[2][1] == 0) {
		cost[2][1] = 100;
		qu.add(new Car(1, 2, -1, 100));
	}
	drive();
       return min;
   }
    private static void drive() {
	int [] dx = {0, 0, 1, -1};
	int [] dy = {1, -1, 0, 0};
	int size = qu.size();
	for (int i = 0; i < size; i++) {
		Car c = qu.poll();
		if(c.x == map.length-2 && c.y == map.length-2) {
			min = Math.min(min, c.cost);
			continue;
		}
			
		for (int j = 0; j < 4; j++) {
			int x = c.x + dx[j];
			int y = c.y + dy[j];
			if(map[y][x] == 0 ) {
				int diff = x - c.x;
				if(diff != 0 && c.direction == 1 && (cost[y][x] >= c.cost + 100 || cost[y][x] == 0)) {
					cost[y][x] = c.cost+100;
					qu.add(new Car(x, y, 1, c.cost+100));
				}
				else if(diff != 0 && c.direction == -1 && (cost[y][x] >= c.cost + 600 || cost[y][x] == 0)) {
					cost[y][x] = c.cost+600;
					qu.add(new Car(x, y, 1, c.cost+600));
				}
				else if(diff == 0 && c.direction == 1 && (cost[y][x] >= c.cost + 600 || cost[y][x] == 0)) {
					cost[y][x] = c.cost+600;
					qu.add(new Car(x, y, -1, c.cost+600));
				}
				else if(diff == 0 && c.direction == -1 && (cost[y][x] >= c.cost + 100 || cost[y][x] == 0)) {
					cost[y][x] = c.cost+100;
					qu.add(new Car(x, y, -1, c.cost+100));
				}
			}
            }
			
	}
	if(qu.isEmpty()) return;
	drive();
}
}