프로그래머스 - 경주로 건설(Java, LV3, 2020 카카오)

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

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

 

틀린 풀이

처음에 생각했던 풀이는 다음과 같다(틀린풀이 주의)

1. BFS로 최단 경로 탐색
2. BFS로 최단 경로를 탐색하며 특정 좌표에 어디서 왔는지를 기록(경로 기록)
3. 경로를 거꾸로 돌아가며 방향이 꺾이면 600원 추가 / 아니면 100원 추가

import java.util.*;

// pair class
class Pair{
    int left;
    int right;
    int dir;
    
    public Pair(int left, int right, int dir){
    	this.left = left;
        this.right = right;
        this.dir = dir;
    }
    
    public void setLeft(int left){ this.left = left;}
    public void setRight(int right){this.right = right;}
    public void setDir(int dir){this.dir = dir;}

    public int getLeft(){return this.left;}
    public int getRight(){return this.right;}
    public int getDir(){return this.dir;}
}

class Solution {
    
    public void bfs(int[][] board, Pair[][] pboard){
        int n = board.length;
        Queue<Pair> q = new LinkedList(); 
        int[][] visit = new int[n][n];
        int[] dx = {-1, 1, 0 , 0}; // UDRL
        int[] dy = {0, 0, 1, -1}; // UDRL
        int cost = 0;
        int x =0; int y=0;
        
        System.out.println(Integer.toString(n-1)+ Integer.toString(n-1)+"FFFF" );
            
        // 탐색
        q.add(new Pair(0,0,-1));
        visit[0][0] = 1;
        while(!q.isEmpty()){
            // 현재 위치
            Pair now = q.poll();
            x = now.getLeft();
            y = now.getRight();
            visit[x][y] = 1;
            
            // 종료 조건 체크
            if (x==n-1 && y==n-1)
                break;
            
            // 갈 수 있으면 추가 U 
            if (x+dx[0]>=0 && x+dx[0]<n && y+dy[0]>=0 && y+dy[0] < n 
                && board[x+dx[0]][y+dy[0]] == 0 & visit[x+dx[0]][y+dy[0]] == 0) {
                q.add(new Pair(x+dx[0],y+dy[0],-1));
                pboard[x+dx[0]][y+dy[0]] = new Pair(x,y,0);
            }
            
            // 갈 수 있으면 추가 D 
           if (x+dx[1]>=0 && x+dx[1]<n && y+dy[1]>=0 && y+dy[1] < n 
                && board[x+dx[1]][y+dy[1]] == 0 & visit[x+dx[1]][y+dy[1]] == 0) {
                q.add(new Pair(x+dx[1],y+dy[1],-1));
                pboard[x+dx[1]][y+dy[1]] = new Pair(x,y,0);
            }
            
            // 갈 수 있으면 추가 R
           if (x+dx[2]>=0 && x+dx[2]<n && y+dy[2]>=0 && y+dy[2] < n 
                && board[x+dx[2]][y+dy[2]] == 0 & visit[x+dx[2]][y+dy[2]] == 0) {
                q.add(new Pair(x+dx[2],y+dy[2],-1));
                pboard[x+dx[2]][y+dy[2]] = new Pair(x,y,1);
            }
            
            // 갈 수 있으면 추가 L 
            if (x+dx[3]>=0 && x+dx[3]<n && y+dy[3]>=0 && y+dy[3] < n 
                && board[x+dx[3]][y+dy[3]] == 0 & visit[x+dx[3]][y+dy[3]] == 0) {
                q.add(new Pair(x+dx[3],y+dy[3],-1));
                pboard[x+dx[3]][y+dy[3]] = new Pair(x,y,1);
            }
            
        }
    } 
    public int solution(int[][] board) {
        int cost = 0;
        int n = board.length;
        int[] dx = {-1, 1, 0 , 0}; // UDRL
        int[] dy = {0, 0, 1, -1}; // UDRL
        Pair[][] pboard = new Pair[n][n];
        
        // BFS 최단경로 구해서
        // 경로 거꾸로 파싱하며 비용 추가
        // 바로 이전 경로 UDRL 중 UD / RL 변경되면 500 추가, 그외 100
        bfs(board, pboard);
        
        // 경로 비용 산정(거꾸로 파싱)
        int x = n-1; int y= n-1;
        int p_dir = -1; int dir = -1;
            
        while(true){
            System.out.println(Integer.toString(x)+ Integer.toString(y) + " dir :  "+ Integer.toString(p_dir) + Integer.toString(dir) + " cost : "+ Integer.toString(cost));
            Pair now = pboard[x][y];
            x =  now.getLeft();
            y =  now.getRight();
            
            p_dir = dir;
            dir =  now.getDir();
            
            
            if(x == 0 & y==0){
                cost+=100;
                break;
            }
            // 비용 계산 (처음 길)
            if(p_dir == -1 && dir == -1){cost+=0;}
            else if (p_dir == -1 && dir != -1){cost+=100;}
                
            // 비용 계산(이전 UD 였는데 RL) 500
            else if (p_dir == 0 && dir ==1)
                cost+=600;
            
            // 비용 계산(이전 RL 였는데 UD) 500
            else if (p_dir == 1 && dir == 0)
                cost +=600;
            
            // 비용 계산(그 외) 100
            else
                cost +=100;
        }
            
        
        return cost;
    }
}

 

 

풀이

그런데, 이렇게 돌아보니 최소값이 나오지도 않았다.

애초에 최단 경로를 탐색하는 것이 아닌 최소비용의 경로를 탐색하는 것이 핵심이었다!

 

그래서 특정 좌표에 이전 경로를 기록하는 것이 아닌, 비용을 계속 기록해가기로 수정했다(애초에 경로가 필요없음).

그리고 방문했던 곳도 다시 갈 수 있다. 왜냐하면 비용을 최소화하는 것이 목적이기에!

(그 외, 다른 사람들의 코드를 보며 익숙치 않았던 자바 문법을 조금 보완했다)

그래서 풀이는 아래와 같다.

 

1. BFS로 탐색을 한다(단, 벽만 아니라면 갔던 곳도 다시 갈 수 있다)
2. 이전 방향을 꺼내보며 현재 탐색중인 방향이 다르면 600원 추가, 같으면 100원 추가(되돌아 가는 경우는 없기에)
3. 특정 좌표에 처음 방문하거나 새롭게 방문하더라도 지금까지의 비용이 더 저렴하다면 비용 갱신
4. Q가 빌 때 까지 반복(도착점에 도착할 때 종료가 아닌 이유는 3번과 동일)

 

import java.util.*;

// Point class
class Point{
    int x;
    int y;
    int dir;
    int cost;
    
    public Point(int x, int y, int dir, int cost){
    	this.x = x;
        this.y = y;
        this.dir = dir;
        this.cost = cost;
    }
}

class Solution {
    public int bfs(int[][] board){
        int n = board.length;
        Queue<Point> q = new LinkedList(); 
        int[] dx = {-1, 1, 0 , 0}; // UDRL
        int[] dy = {0, 0, 1, -1}; // UDRL
        int x =0; int y=0; int dir = -1;
        int cost = 0; int answer = Integer.MAX_VALUE;
                    
        // 탐색
        q.add(new Point(0,0,-1,0));
        
        while(!q.isEmpty()){
            // 현재 위치
            Point now = q.poll();
            x = now.x; y = now.y;
            dir = now.dir; cost = now.cost; 
            
            // 종료 조건 체크
            if (x==n-1 && y==n-1){
                answer = ((cost < answer)? cost : answer);
                continue; // 추가 탐색 필요없음
            }
            
            // U D R L 방향 탐색 
            for(int i =0; i<4; i++){
                int nx = x +dx[i]; int ny = y +dy[i];
                int ncost = 0;
                // 범위 안벗어나고 벽이 아니면
                if (nx>=0 && nx<n && ny>=0 && ny < n  && board[nx][ny] != 1) {
                    // 방향에 따라 비용 산정
                    if (dir == -1 || dir == i){
                        ncost = cost + 100;
                    } else if(dir != i){
                        ncost = cost + 600;
                    }
                    
                    // 처음 방문하거나 더 작은 경우 갱신
                    if(board[nx][ny]==0 || board[nx][ny] >= ncost ){
                        board[nx][ny] = ncost;
                        q.add(new Point(nx,ny,i,ncost));
                    }
                } // if
            } // for
        } // while
        return answer;
    } 
    public int solution(int[][] board) {
        
        // BFS 최단경로 구하기
        // 단, 최단경로를 구할 때, 재방문 가능(비용 기준)
        // 방향을 통해 비용을 더해가며 최종 비용 계산
        return bfs(board);
    }
}