[프로그래머스/자바] 경주로 건설 풀이 - 2020 카카오 인턴십

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

프로그래머스

 

 

2020 카카오 인턴십 Level 3 문제다.

 

 

처음에는 2차원 배열에 최소 값을 저장해나가는 BFS로 구현했는데, 정확도가 떨어졌다.

2차원 배열+ bfs로 풀었을 때의 반례는 아래와 같다.

 

{{0, 0, 0, 0, 0, 0, 0, 0}, 
{1, 0, 1, 1, 1, 1, 1, 0}, 
{1, 0, 0, 1, 0, 0, 0, 0}, 
{1, 1, 0, 0, 0, 1, 1, 1}, 
{1, 1, 1, 1, 0, 0, 0, 0}, 
{1, 1, 1, 1, 1, 1, 1, 0}, 
{1, 1, 1, 1, 1, 1, 1, 0}, 
{1, 1, 1, 1, 1, 1, 1, 0}}

 

(답: 4500)

 

이 때 배열 [3][4]에서 [3][3]에서 오는 경로와 [2][4]에서 오는 경로 두가지가 맞물리는데,

[2][4]에서 오는 경로가 최종적으로는 최소 경로지만,

[3][4] 위치에서는 [3][3]이 더 최소 경로이므로 [3][3]의 경로를 선택하게 된다.

 

 

다른 분의 풀이를 참고해 방향별(상하좌우)로 값을 저장해야 한다는 것을 배웠다.

방향별로 저장하는 것과 3차원 배열 둘다 처음 구현해봤기에 스스로 생각하기가 더 어려웠다.

생각보다 오래 걸린 문제였지만 BFS는 언제나 재밌게 푸는 것 같다.

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

class Solution {
	static int cost[][][];
	// 시계 방향
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int n;
    
    public int solution(int[][] board) {
    	n = board.length;
    	cost = new int[4][n][n];
    	
    	for(int i=0;i<4;i++)
    		for(int j=0;j<n;j++)
    			for(int k=0;k<n;k++)
    				cost[i][j][k] = Integer.MAX_VALUE;
    	
    	BFS(board);
    	
    	int ans = Integer.MAX_VALUE;
    	for(int i=0;i<4;i++)
    		ans = Math.min(ans, cost[i][n - 1][n - 1]);
    	
    	return ans;
    }
    
	static void BFS(int[][] board) {
		Queue<int[]> q = new LinkedList<>();
		
		// 방향, 행, 열
		if(board[0][1] == 0) {
			cost[1][0][1] = 100;
			q.offer(new int[] {1, 0, 1});
		}
		if(board[1][0] == 0) {
			cost[2][1][0] = 100;
			q.offer(new int[] {2, 1, 0});
		}
		
		while(!q.isEmpty()) {
			int[] arr = q.poll();
			int dir = arr[0];
			int x = arr[1];
			int y = arr[2];
			
			if(x == n - 1 && y == n - 1) 
				continue;
			
			for(int nextDir=0;nextDir<4;nextDir++) {
				int nextX = x + dx[nextDir];
				int nextY = y + dy[nextDir];
				
				if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && board[nextX][nextY] == 0) {
					if(dir != nextDir) { 
						if(dir + nextDir == 2 || dir + nextDir == 4) // 역방향
							continue;
						if(cost[nextDir][nextX][nextY] < cost[dir][x][y] + 600)
							continue;
						q.add(new int[] {nextDir, nextX, nextY});
						cost[nextDir][nextX][nextY] = cost[dir][x][y] + 600;
					}
					else {
						if(cost[nextDir][nextX][nextY] < cost[dir][x][y] + 100)
							continue;
						q.add(new int[] {nextDir, nextX, nextY});
						cost[nextDir][nextX][nextY] = cost[dir][x][y] + 100;
					}
				}
			}
		}
	}
}