[프로그래머스] 경주로 건설 (08.26)

문제

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

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

 

접근법

처음에는 dfs로 풀었다.

이전 x좌표를 계속 가지고 가면서 x좌표가 변하면 x를 움직인 것이고, x좌표가 변하지 않으면 y좌표가 움직인 것으로 간주하고 풀었다.

결과적으로는 맞았지만 시간초과가 났다.

그래서 bfs로 풀었다.

visited 배열을 boolean으로 두지않고 int로 두고 최소 비용을 저장하였다.

bfs로 처음 풀다가 직면한 문제는 각 배열에 한 번밖에 진입할 수 없었기 때문에 그걸 처리하는게 어려웠는데

int로 하니 방문하지 않았을 경우와 방문을 하였지만 현재 비용보다 더 큰 비용이 들 경우를 확인하여 q에 저장하였다.

 

코드

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


class Solution {
    private int[][] visited;
    private int answer = Integer.MAX_VALUE;
    int[] moveX = {-1,1,0,0};
    int[] moveY = {0,0,1,-1};
    
    public int solution(int[][] board) {
        visited = board.clone();

        int res = bfs(board);
        
        return res;
    }
    
    public class Pair{
        int x;
        int y;
        int cost;
        int direction;

        public Pair(int x, int y, int cost, int direction) {
            this.x = x;
            this.y = y;
            this.cost = cost;
            this.direction = direction;
        }
    }
    
    public int bfs(int[][] board){
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0, 0, 0, -1));
        visited[0][0] = 1;

        while(!q.isEmpty()) {
            Pair pair = q.poll();
            int x = pair.x;
            int y = pair.y;
            int cost = pair.cost;
            int direction = pair.direction;

            //목적지에 도달할 경우 answer에 값 저장
            if(x == board.length-1 && y == board.length-1){
                answer = Math.min(answer, cost);
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int nextX = x + moveX[i];
                int nextY = y + moveY[i];
                
                if (nextX >= board.length || nextX < 0 || nextY >= board.length || nextY < 0)
                    continue;
                if (visited[nextX][nextY] == 1)
                    continue;

                int nextCost = 0;
                //(0,0)일 경우 또는 이전과 같은 방향으로 움직인 경우에는 직선
                if(direction == -1 || direction == i)
                    nextCost = cost + 100;
                //이전과는 다른 방향으로 움직일 경우 코너
                else if(direction != i)
                    nextCost = cost + 600;

                //한 번도 방문하지 않았거나 방문했지만 최소비용이 아닐 경우
                if(visited[nextX][nextY] == 0 || visited[nextX][nextY] >= nextCost){
                    //최소 비용을 갱신해주고 q에 저장
                    visited[nextX][nextY] = nextCost;
                    q.add(new Pair(nextX, nextY, nextCost, i));
                }

            }
        }
        return answer;
    }
}