Programmers - 경주로 건설 with JAVA

 

문제

맵이 주어지고 왼쪽 위 끝에서 오른쪽 아래 끝까지 도달한다. 맵에는 길이 있고 벽이 있다. 벽을 피해서 지나야 한다. 또한 직선 도로로 갈 시 100, 한번 꺾을 때마다 500의 cost가 발생한다. 가장 적은 cost를 사용하여 목표지점까지 도달한다.

 

 

 

로직

기존의 유사한 문제와 다른 점은 cost 조건이 상이하다는 점과 벽이 존재하는데 기존의 방문한 곳을 재방문 하는 것을 방지하는 로직이나 현재 확인하고자 하는 cost 보다 작으면 방문하지 않는 로직을 그대로 사용할 수 없다는 점이다. 그렇다면 결과적으로 최소값을 구할 수 없기 때문이다. 따라서 cost보다 작으면 방문하지 않는 로직을 사용하되, 기존보다 유하게 cost 판단을 해 이를 해결하였다.

 

 

 

코드1

import java.util.*;
class Solution {
    public int solution(int[][] board) {
        int x_len = board.length;
        int y_len = board[0].length;
        for(int x=0; x<x_len; x++){
            for(int y=0; y<y_len; y++){
                if(board[x][y] != 1){
                    board[x][y] = (int)1e9;   
                }
            }
        }
        board[0][0] = 0;
        PriorityQueue<List<Integer>> queue = new PriorityQueue<>(Comparator.comparing(arr -> arr.get(0)));
        if(board[0][1] != 1){
            queue.add(Arrays.asList(100, 0, 1, 0));   
            board[0][1] = 100;
        }
        if(board[1][0] != 1){
            queue.add(Arrays.asList(100, 1, 0, 1));   
            board[1][0] = 100;
        }
        int[] dx = {0, 1, -1, 0};
        int[] dy = {-1, 0, 0, 1};
        while(queue.size() > 0){
            List<Integer> now = queue.poll();
            int cost = now.get(0);
            int x = now.get(1);
            int y = now.get(2);
            int direction = now.get(3);
            for(int i=0; i<4; i++){
                int next_x = x + dx[i];
                int next_y = y + dy[i];
                int next_direction = -1;
                int next_cost = cost;
                if(next_x<0 | next_x>=x_len | next_y<0 | next_y>=y_len){
                    continue;
                }
                if(board[next_x][next_y] == 1){
                    continue;
                }
                if(board[next_x][next_y] < cost-200){
                    continue;
                }
                if(i == 3 | i == 0){
                    if(direction == 0){
                        board[next_x][next_y] = Math.min(board[next_x][next_y], cost+100);
                        next_cost += 100;
                    }
                    else{
                        board[next_x][next_y] = Math.min(board[next_x][next_y], cost+600);
                        next_cost += 600;
                    }
                    next_direction = 0;
                }
                else{
                    if(direction == 0){
                        board[next_x][next_y] = Math.min(board[next_x][next_y], cost + 600);
                        next_cost += 600;
                    }
                    else{
                        board[next_x][next_y] = Math.min(board[next_x][next_y], cost + 100);
                        next_cost += 100;
                    }
                    next_direction = 1;
                }
                queue.add(Arrays.asList(next_cost, next_x, next_y, next_direction));
            }
        }
        return board[x_len-1][y_len-1];
    }
}

 

 

 

코드2

import java.util.*;
class Solution {
    public int solution(int[][] board) {
        int n = board.length;
        int m = board[0].length;
        for(int x=0; x<n; x++){
            for(int y=0; y<m; y++){
                if(board[x][y] == 1){
                    board[x][y] = -1;
                }
                if(board[x][y] == 0){
                    board[x][y] = (int)1e9;
                }
            }
        }
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        board[0][0] = 0;
        PriorityQueue<List<Integer>> queue 
            = new PriorityQueue<>(Comparator.comparing(arr -> arr.get(0)));
        queue.add(Arrays.asList(0, 0, 0, 0));
        queue.add(Arrays.asList(0, 0, 0, 1));
        while(queue.size() > 0){
            List<Integer> now = queue.poll();
            int cost = now.get(0);
            int x = now.get(1);
            int y = now.get(2);
            int direction = now.get(3);
            if(board[x][y] <= cost-600){
                continue;
            }
            for(int i=0; i<4; i++){
                int next_x = x+dx[i];
                int next_y = y+dy[i];
                int next_cost = cost;
                int next_direction = direction;
                if(next_x < 0 | next_x >= n | next_y < 0 | next_y >= m){
                    continue;
                }
                if(board[next_x][next_y] == -1){
                    continue;
                }
                if(direction == 0){
                    if(i == 1 | i == 3){
                        next_cost += 100;
                    }
                    else{
                        next_cost += 600;
                        next_direction = 1;
                    }
                }
                if(direction == 1){
                    if(i == 1 | i == 3){
                        next_cost += 600;
                        next_direction = 0;
                    }
                    else{
                        next_cost += 100;
                    }
                }
                if(board[next_x][next_y] <= next_cost-600){
                    continue;
                }
                board[next_x][next_y] 
                    = Math.min(board[next_x][next_y], next_cost);
                queue.add(Arrays
                          .asList(next_cost, next_x, next_y, next_direction));
            }
        }
        return board[n-1][m-1];
    }
}