[Programmers] 경주로 건설

문제

 

2020 카카오 인턴십 > 경주로 건설

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

 

 

아이디어

 

이번 문제의 아이디어는 BFS입니다.

 

DFS로 시도하려고 하시는 분들도 있을 것 같아 보이는데 개인적인 견해로는 배열의 크기가 최대 25이기 때문에 시간 초과가 발생될 것으로 보입니다.

 

그렇기 때문에 BFS 사용을 추천드립니다.

 

문제를 풀기 위해 제가 추가적으로 고려한 것은 다음과 같습니다.

 

1. 방향을 꺾는 여부에 따라 다른 처리

2. 한 번 방문한 곳은 최소비용을 배열에 저장

 

이 두 가지를 생각하며 문제를 풀면 충분히 푸실 수 있으실 것입니다.

 

 

구현 코드 (Java)

 

import java.util.*;

class Solution {
    public int solution(int[][] board) {
        // 방향은 인덱스 순서대로 {우, 하, 좌, 상}
    	int dirj[] = {1, 0, -1, 0}; // j방향
    	int diri[] = {0, 1, 0, -1}; // i방향
    	int n = board.length;
        int visited[][] = new int[n][n]; // 해당 좌표까지 도달할 수 있는 최소 비용을 저장
        Queue<Node> queue = new LinkedList<Node>();
        
        for(int i=0; i<n; i++) {
        	for(int j=0; j<n; j++) {
        		visited[i][j] = Integer.MAX_VALUE; // MAX값으로 초기화
        	}
        }
        
        visited[0][0] = 0; // 초기위치는 최소 비용 0
        
        if(board[0][1] == 0) { // [0][1]에 길이 있을 경우
        	queue.add(new Node(0, 1, 100, 0)); // 이동방향은 우측
        	visited[0][1] = 100;
        }
        
        if(board[1][0] == 0) { // [1][0]에 길이 있을 경우
        	queue.add(new Node(1, 0, 100, 1)); // 이동방향은 아래
        	visited[1][0] = 100;
        }
        
        while(!queue.isEmpty()) {
        	Node node = queue.poll();
        	
        	if(node.cost > visited[node.i][node.j]) { // 현재 비용이 저장되어 있던 최소비용보다 크다면
        		continue;
        	}
        	
        	visited[node.i][node.j] = Math.min(visited[node.i][node.j], node.cost); // 최소값 저장
        	
        	if(node.i == n-1 && node.j == n-1) { // 목표위치에 도달한 경우
        		continue;
        	}
        	
        	for(int a=0; a<4; a++) {
        		int nexti = node.i + diri[a];
        		int nextj = node.j + dirj[a];
        		
        		if(nexti >= n || nexti < 0 || nextj >= n || nextj < 0 || board[nexti][nextj] == 1) { // 배열을 벗어나거나 벽인 경우
        			continue;
        		}
        		
        		if(Math.abs(node.dir - a)%2 == 1) { // 방향을 꺾을 경우, 길 + 코너
        			if(node.cost+600 >= visited[nexti][nextj]) {
        				continue;
        			}
        			
        			queue.add(new Node(nexti, nextj, node.cost+600, a));
        		} else {
        			if(node.cost+100 >= visited[nexti][nextj]) { // 방향을 꺾지 않을 경우, 길
        				continue;
        			}
        			
        			queue.add(new Node(nexti, nextj, node.cost+100, a));
        		}
        	}
        }
        
        return visited[n-1][n-1];
    }
    
    private static class Node {
    	int i, j, cost, dir;

		public Node(int i, int j, int cost, int dir) {
			this.i = i;
			this.j = j;
			this.cost = cost;
			this.dir = dir;
		}
    }
}

 

 

읽어주셔서 감사합니다.