[Programmers] 2020 카카오 인턴십 4번 - 경주로 건설

[문제 설명]

2차원 배열 board가 주어진다.

0은 비어있고, 1은 막혀있다.

시작점 (0, 0) 부터 (N-1, N-1) 까지 잇는 경주로를 건설할 때, 최소 비용을 구하는 문제

 

[조건]

3 <= Len (board) <= 25

board 배열의 각 원소는 0 또는 1

항상 경주로를 건설할 수 있는 형태로 주어짐

직선 경주로 건설 비용은 100원, 직각으로 경주로가 건설되는 경우 500원의 추가 비용

 

[풀이 과정]

이차원 배열에서 최단 경로, 최단 시간을 찾는 전형적인 BFS, DFS 문제.

해당 문제의 특이점은 직각 경주로를 건설에 비용이 더 소요된다는 점이다.

 

이 때문에 흔히 사용하는 int visit[N][N]의 형태로 방문 여부를 체크하면 안된다.

왜냐하면 최소 비용이 아닌 상태로 (i, j)에 도착하였더라도, 다음 점 (i, j + 1) 에 최소 비용으로 도착할 수 있기 때문이다.

 

따라서 문제 해결을 위해서 2가지를 신경써야 한다.

 

1. 탐색시 이전의 이동 방향 저장 (코드의 via 변수)

2. 각 방향별 최소 비용 저장 (코드의 minimumCost 배열)

 

 

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

public class Programmers_kakao2020_intern_4 {
	
	static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 시계 방향 (상, 우, 하, 좌)
	static int[][][] minimumCost;                            // 각 점에서 네 방향으로 나갈 때 비용 최소값 저장
	
	static class info {
		int prevI;
		int prevJ;
		int via;
		int cost;
		
		public info(int prevI, int prevJ, int via, int cost) {
			super();
			this.prevI = prevI;
			this.prevJ = prevJ;
			this.via = via;
			this.cost = cost;
		}
	}
	
	public static int solution(int[][] board) {
        int answer = (1 << 30);
        minimumCost = new int[board.length][board.length][4];
        Queue<info> q = new LinkedList<> ();
        
        // 초기값 세팅
        for (int i = 0; i < board.length; ++i) {
        	for (int j = 0; j < board.length; ++j) {
        		Arrays.fill(minimumCost[i][j], (1 << 30));
        	}
        }
        
        // 시작지점에서 오른쪽
        if (board[0][1] != 1) {
        	q.add(new info(0, 0, 1, 100));
        	minimumCost[0][0][1] = 100;
        }
        
        // 시작지점에서 아래쪽
        if (board[1][0] != 1) {
        	q.add(new info(0, 0, 2, 100));
        	minimumCost[0][0][2] = 100;
        }
        
        while (!q.isEmpty()) {
        	info cur = q.poll();
        	int ci = cur.prevI + dir[cur.via][0];
        	int cj = cur.prevJ + dir[cur.via][1];
        	int cv = cur.via;
        	int cc = cur.cost;
        	int ni, nj, nv, nc;
        	
        	if (ci == board.length - 1 && cj == board.length - 1) {
        		answer = (answer < cc) ? answer : cc;
        		continue;
        	}
        	
        	for (int d = 0; d < 4; ++d) {
        		ni = ci + dir[d][0];
        		nj = cj + dir[d][1];
        		
        		// 범위 밖 or 벽
        		if (ni < 0 || nj < 0 || ni >= board.length || nj >= board.length || board[ni][nj] == 1) {
        			continue;
        		}
        		
        		// 방향 조건문 시작
        		// (1) 왔던 길 다시 가면 skip
        		if (d == ((cv + 2) % 4))
        			continue;
        		
        		// (2) 직선 방향 (0원) or 수직 방향 (500원)
    			nc = cc + 100 + ((d == cv) ? 0 : 500);
    			
    			if (minimumCost[ci][cj][d] > nc) {
    				minimumCost[ci][cj][d] = nc;
    				q.add(new info(ci, cj, d, nc));
    			}
        	}
        }
        return answer;
    }
	
   public static void main(String[] args) {
	   System.out.println(solution(new int[][]{{0,0,0}, {0,0,0},{0,0,0}}));
   }
}

 

 

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

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

 

 

<유사한 문제>

https://b2narae.tistory.com/11

[Programmers] 2020 카카오 블라인드 채용 7번 - 블록 이동하기