프로그래머스_카카오인턴십_경주로건설_자바

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

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

 

 

출처 : 프로그래머스

문제를 보면 n * n 배열판에서 (0, 0) => (n - 1, n - 1) 로 가는 최소비용을 구하는 문제이다.

위 그림과 같이 직선도로는 100원 코너는 500 원이 소요된다.

처음에 DFS 로 풀이를 했지만 시간초과가 나와 BFS 로 풀이했다. 

풀이방법!

탐색을 진행하면서 현재의 방향 정보를 저장해준다. (현재 자동차의 위치, 비용, 방향을 담고있는 객체 선언)

기본적인 BFS 와 다른점은 이미방문한곳도 비용이 더적게 든다면 방문할수있다는 것이다. 

위와같은 방식으로 목적지에 도달할때까지의 비용정보를 갱신해주면서 최소비용을 구하면 된다.

 

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

	static int min = Integer.MAX_VALUE;
	static int xx[] = {-1, 0, 1, 0};
	static int yy[] = {0, -1, 0, 1};
	static int map[][];
	static int n;
	static int answer;
	
    public static int solution(int[][] board) {
        answer = Integer.MAX_VALUE;
        n = board.length;
        map = board;
        
        // 초기 방향을 -1 을 주는 이유는 자동차가 시작할때 오른쪽과 아래로 둘다 이동할수 있기 떄문이다.
        bfs(0, 0, 0, -1);
        return answer;
    }   
    
    public static void bfs(int x, int y, int cost, int dir) {
    	
    	Queue<Road> q = new LinkedList<Road>();
    	q.add(new Road(x, y, cost, dir));
    	// 출발지점을 1 로 바꾸어 탐색에서 제외한다.
    	map[x][y] = 1;
    	
    	while(!q.isEmpty()) {
    		
    		
    		Road temp = q.poll();
    		// 목적지에 도착했다면 최소비용을 갱신해준다.
    		if(temp.x == n - 1 && temp.y == n - 1) {
    			answer = Math.min(answer, temp.cost);
    			continue;
    		}
    
    		// 4방향으로 이동할수있다 .
    		for(int i = 0; i < 4; i++) {
    			int new_x = temp.x + xx[i];
    			int new_y = temp.y + yy[i];
    			// 새로 이동하는 곳은 범위안이고 벽이(1) 아니여야한다.
    			if(new_x >= 0 && new_x < n && new_y >= 0 && new_y < n && map[new_x][new_y] != 1) {
    				int new_cost = 0;
    				// 새로운 지점의 비용구하기.
    				if(temp.dir == -1 || temp.dir == i) {
    					new_cost = temp.cost + 100;
    				}else if(temp.dir != i){
    					new_cost = temp.cost + 600;
    				}
    			
    				//처음가는 곳이라면 정보를 넣어주면된다.
    				if(map[new_x][new_y] == 0) {
    					map[new_x][new_y] = new_cost;
    					q.add(new Road(new_x, new_y, new_cost, i));
    				}else if(map[new_x][new_y] >= new_cost) { //처음가지않는 곳이라면 비용이 더작거나 같은 경우 넣어주면된다.
    					map[new_x][new_y] = new_cost;
    					q.add(new Road(new_x, new_y, new_cost, i));
    				}
    				
    				
    			}
    		}
    		
    	}
    }
}


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