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

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

문제

해당 문제는 2차원으로 map가 주어졌을 때 0,0부터 N-1, N-1까지 최소 비용으로 연결하는 값을 구하는 문제다.

단 직선 도로의 경우 비용이 100 추가되고 곡선의 경우 500이 추가된다. (사실 곡선은 곡선 + 직선 도로임 즉 + 600)

조건

• board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
• board 배열의 각 원소의 값은 0 또는 1 입니다.
  • 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
  • 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
• board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
• 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.

풀이

처음 해당 문제를 접했을 때는 bfs를 하면 되겠다고 생각했으나 문제를 풀다 보니 막히는 부분이 있었고, 이에 대해서 우선순위 큐를 이용해 해결을 했지만 결론적으로 최종 테케에서는 모두 맞추지 못했고, 질문하기를 참고하여 3차원 배열을 통해 방문을 체크해야 한다는 걸 알게 되어 3차원 배열을 이용해 문제를 해결했다.

3차원 배열에서는 좌표값과 이동 방향을 같이 체크하고 거기에 대한 건설비용을 갱신해주면 된다.

먼저 처음 3차원 배열을 최댓값으로 초기화하고, 0,0에서 오른쪽, 아래로 이동 가능한지 체크에 큐에 담아준 뒤 bfs를 돌려준다. bfs에서는 직선과 곡선을 나누고 직선에서 가려는 곳이 지금 + 건설비용보다 클 경우만 이동시켜준다.

코드

import java.util.*;
 
class Solution {
    
	static int N;
	static int[][][] cnt;
	static int[] dy = {-1,1,0,0}, dx = {0,0,-1,1}; //상하좌우
	static Queue<Node> q = new LinkedList<>();
    public static int solution(int[][] board) {
    	N = board.length;
    	cnt = new int[N][N][4]; // 3차원 배열 좌표 방향으로 이동정보 저장
    	for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < 4; k++) {
					cnt[i][j][k] = Integer.MAX_VALUE; // 일단 이동해야하는 곳들을 최대값으로 갱신한다.
				}
			} 
		}
    	if(board[0][1] == 0) { // 0,0에서 오른쪽 갈수있으면 직진하고 큐에담음
    		cnt[0][1][3] = 100; 
    		q.add(new Node(0,1,3));
    	}
    	if(board[1][0] == 0) { // 0,0에서 아래 갈수있으면 직진하고 큐에담음
    		cnt[1][0][1] = 100;
    		q.add(new Node(1,0,1));
    	}
    	bfs(board); //bfs 돌림
    	int answer = cnt[N-1][N-1][0]; // 방향별 최종값중 최소값 찾기
    	for (int k = 1; k < 4; k++) {
			answer = Math.min(answer, cnt[N-1][N-1][k]);
		}
    	return answer;
    }
	
	private static void bfs(int[][] board) {
		while(!q.isEmpty()) {
			Node n = q.poll();
			for (int i = 0; i < 4; i++) {
				int ny = n.y + dy[i];
				int nx = n.x + dx[i];
				if(ny < 0 || nx < 0 || ny >= N || nx >= N || board[ny][nx] == 1) // 배열 범위 벗어나거나 벽인경우
					continue;
				if (i == n.d) { // 직진
					if(cnt[ny][nx][i] > cnt[n.y][n.x][n.d]+100) { // 가려는 곳이 클경우 갱신 필요
						cnt[ny][nx][i] = cnt[n.y][n.x][n.d]+100;
						q.offer(new Node(ny,nx,i));
					}
				} else { // 곡선
					if(cnt[ny][nx][i] > cnt[n.y][n.x][n.d]+600) { // 가려는 곳이 클경우 갱신 필요
						cnt[ny][nx][i] = cnt[n.y][n.x][n.d]+600;
						q.offer(new Node(ny,nx,i));
					}
				}
			}
		}
	}

	static class Node{
		int y, x, d;
		Node(int y, int x,  int d){
			this.y = y;
			this.x = x;
			this.d = d;
		}
	}
}

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드