[틀림] 프로그래머스 경주로 건설 // 다익스트라, 0-1 bfs, 비용으로 가지치기

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

프로그래머스

 

시도1

가중치가 다른 ? -> 다익? 

dfs로 되지 않나? 한번 해보자.

gok 함수에 그림에 있는 경우만 곡선으로 체크 시도

 

시도2

gok 함수에 이전방향을 기준으로 빼먹은 경우의수 추가

import java.util.*;

class Solution {
    static boolean vis[][] = new boolean[26][26];
    static int board[][] = new int[26][26];
    static int ret=987654321;
    static int dy[] = {0,1,0,-1};
    static int dx[] = {1,0,-1,0};
    static int dp[][][][] = new int[26][26][26][26]; //(좌표, 이전방향) 값 : 그때 최소비용
    int n;
    
    boolean gok(int py, int px, int y, int x, int ny, int nx){
        if(py==y && px+1==x && x==nx && y+1==ny) return true;
        if(py==y && px+1==x && x==nx && y-1==ny) return true;
        
        if(py+1==y && px==x && x+1==nx && y==ny) return true;
        if(py+1==y && px==x && x-1==nx && y==ny) return true;
        
        if(py-1==y && px==x && x-1==nx && y==ny) return true;
        if(py-1==y && px==x && x+1==nx && y==ny) return true;
        
        if(py==y && px-1==x && x==nx && y+1==ny) return true;
        if(py==y && px-1==x && x==nx && y-1==ny) return true;
        
        return false;
    }
    int dfs(int y, int x, int py, int px){
        if(y==n-1 && x==n-1){
            // ret = Math.min(ret,cost);
            return 0;
        }
        
        int ret;
        ret = dp[y][x][py][px];
        if(ret!=987654321){
            return ret;
        }
        
        vis[y][x]=true;
        for(int i=0;i<4;++i){
            int ny=y+dy[i];
            int nx=x+dx[i];
            if(ny<0||nx<0||ny>=n||nx>=n) continue;
            if(vis[ny][nx]) continue;
            if(board[ny][nx]==1) continue;
            if(gok(py,px,y,x,ny,nx)){
                ret = Math.min(ret, dfs(ny,nx,y,x)+500+100); //곡선에는 직선도 같이 생김
            }
            else{
                ret = Math.min(ret, dfs(ny,nx,y,x)+100); 
            }
            
        }
        vis[y][x]=false;
        
        dp[y][x][py][px] = ret;
        return ret;
    }
    
    public int solution(int[][] _board) {
        board=_board;
        n=_board.length;
        for(int a = 0; a < 26; a++) {
            for(int b = 0; b < 26; b++) {
                for(int c = 0; c < 26; c++) {
                    for(int d = 0; d < 26; d++) {
                        dp[a][b][c][d] = 987654321;
                    }
                }
            }
        }
        ret = dfs(0,0,0,0);
        System.out.println(gok(0,1,0,2,1,2));
        System.out.println(gok(0,4,0,5,1,5));
        System.out.println(gok(1,5,2,5,2,4));
        System.out.println(gok(2,5,2,4,3,4));
        return ret;
    }
}

원인 : dp의 차원이 너무커서?

 

시도3

상태를 줄여보기

import java.util.*;

class Solution {
    static boolean vis[][] = new boolean[26][26];
    static int board[][] = new int[26][26];
    static int ret=987654321;
    static int dy[] = {0,1,0,-1}; // 우, 아래, 
    static int dx[] = {1,0,-1,0}; 
    static int dp[][][] = new int[26][26][5]; //(좌표, 이전방향) 값 : 그때 최소비용
    int n;
    
    int dfs(int y, int x, int dir){
        if(y==n-1 && x==n-1){
            // ret = Math.min(ret,cost);
            return 0;
        }
        
        int ret;
        ret = dp[y][x][dir];
        if(ret!=987654321){
            return ret;
        }
        
        vis[y][x]=true;
        for(int i=0;i<4;++i){
            int ny=y+dy[i];
            int nx=x+dx[i];
            if(ny<0||nx<0||ny>=n||nx>=n) continue;
            if(vis[ny][nx]) continue;
            if(board[ny][nx]==1) continue;
            if(dir!=i){ //처음이아니고, 방향이 다르면, 곡선임
                ret = Math.min(ret, dfs(ny,nx,i)+500+100); //곡선에는 직선도 같이 생김
            }
            else{
                ret = Math.min(ret, dfs(ny,nx,i)+100); 
            }
            
        }
        vis[y][x]=false;
        
        dp[y][x][dir] = ret;
        return ret;
    }
    
    public int solution(int[][] _board) {
        board=_board;
        n=_board.length;
        for(int a = 0; a < 26; a++) {
            for(int b = 0; b < 26; b++) {
                for(int c = 0; c < 5; c++) {
                    dp[a][b][c] = 987654321;
                }
            }
        }
        ret = Math.min(dfs(0,0,0),dfs(0,0,1));

        return ret;
    }
}

여전히 시간초과..

 

시도4

bfs

import java.util.*;

class A{
    int y;
    int x;
    int dir;
    int cost;
    A(int y, int x, int dir, int cost){
        this.y=y;
        this.x=x;
        this.dir=dir;
        this.cost=cost;
    }
}

class Solution {
    static boolean vis[][] = new boolean[26][26];
    static int board[][] = new int[26][26];
    static int ret=987654321;
    static int dy[] = {0,1,0,-1}; // 우, 아래, 
    static int dx[] = {1,0,-1,0}; 
    static int dp[][][] = new int[26][26][5]; //(좌표, 이전방향) 값 : 그때 최소비용
    int n;
    
    public int solution(int[][] _board) {
        board=_board;
        n=_board.length;
        for(int a = 0; a < 26; a++) {
            for(int b = 0; b < 26; b++) {
                for(int c = 0; c < 5; c++) {
                    dp[a][b][c] = 987654321;
                }
            }
        }
        // ret = Math.min(dfs(0,0,0),dfs(0,0,1));
        
        Queue<A> q = new LinkedList<>();
        q.add(new A(0,0,0,0));
        // q.add(new A(0,0,1,0));
        vis[0][0]=true;
        
        while(q.size()>0){
            int y = q.peek().y;
            int x = q.peek().x;
            int dir = q.peek().dir;
            int cost = q.peek().cost;
            q.remove();
            // vis[y][x]=true;
            
            // System.out.println(y+" "+x + " ");
            
            if(y==n-1 && x==n-1){
                ret=cost;
                break;
            }
            
            for(int i=0;i<4;++i){
                int ny=y+dy[i];
                int nx=x+dx[i];
                if(ny<0||nx<0||ny>=n||nx>=n) continue;
                if(vis[ny][nx]) continue;
                if(board[ny][nx]==1) continue;
                if(dir!=i){ //방향이 다르면, 곡선임
                    // ret = Math.min(ret, dfs(ny,nx,i)+500+100); //곡선에는 직선도 같이 생김
                    q.offer(new A(ny,nx,i,cost+500+100));
                }
                else{
                    // ret = Math.min(ret, dfs(ny,nx,i)+100); 
                    q.offer(new A(ny,nx,i,cost+100));
                }
                vis[ny][nx]=true;
            
            }
        }

        return ret;
    }
}

결과는 오답

원인 : 한번 방문한곳은 방문안하는 특징

해결 : 다익스트라 또는 0-1 bfs를 써야함

기존 BFS 알고리즘으로는 한번 방문한 칸은 다시 방문하지 못한다. 이 때문에 탐색시, 건설 최소비용인 경주로를 방문하지 않고, 방문하지 않았던 칸만 방문하며 비용을 계산하는 문제가 발생한다.

이를 해결하기 위해 방문여부를 저장하는check 배열에 현재까지 계산한 최소 건설비용을 저장하여 메모이제이션을 한다. 이로써 이후에 같은 칸을 방문시 건설 비용을 비교할 수 있게하고 기존 건설비용보다 비용이 적게든다면 다시 방문할 수 있게한다. 최종적으로는 check배열의 (N-1, N-1) 칸에 경주로의 최소건설비용이 저장된다.

 

정답1

비용기반 bfs (유사 0-1 bfs?)

방문배열대신, 비용이 싼경우 재방문 허용해야함.

check[y][x][dir]: (y,x)칸에 dir 방향으로 도착했을 때의 최소 비용, 무한대로 초기화 // 이걸 방문표시 대용으로 사용

y==n-1에 도착했을시, 끝내면 안됨, 정답만 갱신해주고 계속 탐색해야함

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

class A {
    int y, x, dir, cost;
    A(int y, int x, int dir, int cost) {
        this.y = y;
        this.x = x;
        this.dir = dir;
        this.cost = cost;
    }
}

class Solution {
    static final int INF = Integer.MAX_VALUE;
    // 우, 하, 좌, 상
    static final int[] dy = {0, 1, 0, -1};
    static final int[] dx = {1, 0, -1, 0};

    public int solution(int[][] board) {
        int n = board.length;
        // check[y][x][dir]: (y,x)칸에 dir 방향으로 도착했을 때의 최소 비용
        int[][][] check = new int[n][n][4];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                Arrays.fill(check[i][j], INF);

        Queue<A> q = new LinkedList<>();
        // 출발점(0,0)을 우(R=0)와 하(D=1) 방향 두 가지로 초기화
        check[0][0][0] = 0;
        check[0][0][1] = 0;
        q.offer(new A(0, 0, 0, 0));
        q.offer(new A(0, 0, 1, 0));

        int answer = INF;
        while (!q.isEmpty()) {
            A cur = q.poll();
            int y = cur.y, x = cur.x, dir = cur.dir, cost = cur.cost;

            // 도착 지점이라면 최소값 갱신
            if (y == n - 1 && x == n - 1) {
                answer = Math.min(answer, cost);
            }

            // 4방향 탐색
            for (int nd = 0; nd < 4; nd++) {
                int ny = y + dy[nd], nx = x + dx[nd];
                if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                if (board[ny][nx] == 1) continue;

                // 방향이 같으면 직선(100), 다르면 곡선(100+500)
                int add = (nd == dir ? 100 : 600);
                int nc = cost + add;

                // 이전에 이 방향으로 왔을 때보다 비용이 작으면 갱신 후 재방문
                if (nc < check[ny][nx][nd]) {
                    check[ny][nx][nd] = nc;
                    q.offer(new A(ny, nx, nd, nc));
                }
            }
        }

        return answer;
    }
}

 

* 풀이2 (다익스트라)

가중치가 다른 최단거리 최소비용은? 다익스트라

dist[y][x][dir]: (y, x) 위치에 dir 방향으로 도달했을 때의 최소 비용, 초기값은 무한대

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    static final int INF = Integer.MAX_VALUE;
    static class Node {
        int y, x, dir, cost;
        Node(int y, int x, int dir, int cost) {
            this.y = y; this.x = x; this.dir = dir; this.cost = cost;
        }
    }

    public int solution(int[][] board) {
        int n = board.length;
        int[][][] dist = new int[n][n][4];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                Arrays.fill(dist[i][j], INF);

        PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.cost - b.cost);
        // 시작점 (우, 아래)
        for (int d = 0; d < 2; d++) {
            dist[0][0][d] = 0;
            pq.offer(new Node(0, 0, d, 0));
        }

        // 이동 방향 정의 (우, 아래, 왼, 위)
        int[] dy = {0, 1, 0, -1};
        int[] dx = {1, 0, -1, 0};

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            
            // 현재 상태가 이미 더 높은 비용 -> 큐에서 뽑은게 쓸모없음 -> 버림
            if (cur.cost != dist[cur.y][cur.x][cur.dir]) continue; //느긋한삭제 안해도 통과하긴 함
            
            for (int nd = 0; nd < 4; nd++) {
                int ny = cur.y + dy[nd], nx = cur.x + dx[nd];
                if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                if (board[ny][nx] == 1) continue;

                int w = (nd == cur.dir ? 100 : 600);
                int nc = cur.cost + w;
                if (nc < dist[ny][nx][nd]) { //계산한 다음비용 < 저장된 다음비용 -> 저장된거보다 더싸므로 탐색 ㄱㄱ
                    dist[ny][nx][nd] = nc;
                    pq.offer(new Node(ny, nx, nd, nc));
                }
            }
        }

        // 도착점 (n-1, n-1) 네 방향 중 최소값 반환
        int answer = INF;
        for (int d = 0; d < 4; d++) {
            answer = Math.min(answer, dist[n-1][n-1][d]);
        }
        return answer;
    }
}

다음날 다시푼 다익스트라

import java.util.Arrays;
import java.util.PriorityQueue;


class Solution {
    class A{
        int y;
        int x;
        int cost;
        int dir;
        A(int y, int x, int cost, int dir){
            this.y=y;
            this.x=x;
            this.cost=cost;
            this.dir=dir;
        }
    }
    
    // 이동 방향 정의 (우, 아래, 왼, 위)
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static int[][][] dist = new int[26][26][4];
    static int answer;
    static int n;
    static PriorityQueue<A> pq = new PriorityQueue<>((a,b)->a.cost-b.cost);
    
    public int solution(int[][] board) {
        int n = board.length;
        
        //무한대로 초기화
        for(int i=0;i<26;++i){
            for(int j=0;j<26;++j){
                for (int k = 0; k < 4; k++) {
                    dist[i][j][k] = 987654321;
                }
            }
        }
        
        //초기값
        dist[0][0][0]=0;
        dist[0][0][1]=0;
        pq.offer(new A(0,0,0,0));
        pq.offer(new A(0,0,0,1));
        
        while(pq.size()>0){
            A cur = pq.poll();
            int y = cur.y;
            int x = cur.x;
            int cost = cur.cost;
            int dir = cur.dir;
            
            // System.out.println(y+ " " +x+ " " +cost+ " " +dir);
            
            for(int i=0;i<4;++i){
                int ny=y+dy[i];
                int nx=x+dx[i];
                int ndir=i;
                int ncost=cost;
                if(dir!=ndir){
                    ncost+=600; //곡선 + 직선
                }
                else{
                    ncost+=100; //직선
                }
                   
                if(ny<0 || nx<0 || ny>=n || nx>=n) continue;
                if(board[ny][nx]==1) continue;

                // //느긋한삭제
                // if(ncost!=dist[ny][nx][ndir]) continue;
                
                if(ncost < dist[ny][nx][ndir]){
                    dist[ny][nx][ndir] = ncost;
                    pq.offer(new A(ny,nx,ncost,ndir));
                }
            }
        }
        
        answer=987654321;
        for(int i=0;i<4;++i){
            answer = Math.min(answer,dist[n-1][n-1][i]);
            System.out.println(dist[n-1][n-1][i]);
        }
        
        return answer;
    }
}

느긋한 삭제하려면 for문 위에서 하면 됨.

느긋한 삭제 안하는경우

느긋한삭제 하는경우

pq 커스텀 정렬방법

1. Comparable 구현. 복잡

static class Node implements Comparable<Node> {
        int y, x, dir, cost;
        Node(int y, int x, int dir, int cost) {
            this.y = y; this.x = x; this.dir = dir; this.cost = cost;
        }
        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.cost, o.cost);
        }
    }

2. 람다 good

PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.cost - b.cost);

 

 

* dfs + 가지치기(?)

vis에 비용을저장

저장된비용 < 현재 비용이 더크다면, 저장된걸쓰면됨 -> 탐색안하기

#include <string>
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <string.h>

using namespace std;
unsigned int visited[25][25][4];
int dy[] = {1, 0, -1, 0}; //down, right, up, left
int dx[] = {0, 1, 0, -1};
unsigned int result = -1;
void dfs(vector<vector <int>> &map, int N, int y, int x, int dir, unsigned int cur_cost) {
    if (y < 0 || y >= N || x < 0 || x >= N || map[y][x] == 1 || visited[y][x][dir] < cur_cost) {
        return;
    }
    visited[y][x][dir] = cur_cost;
    if (y == N - 1 && x == N - 1) {
        if (result > cur_cost) {
            result = cur_cost;
        }
        return;
    }
    for (int i = 0; i < 4; i++) {
        int dirIdx = (dir + i) % 4;
        int ny = y + dy[dirIdx];
        int nx = x + dx[dirIdx];
        if (i == 0) {
            dfs(map, N, ny, nx, dirIdx, cur_cost + 100);
        }
        else {
            dfs(map, N, ny, nx, dirIdx, cur_cost + 600);
        }
    }

}
int solution(vector<vector<int>> board) {
    memset(visited, -1, sizeof(visited));
    dfs(board, board[0].size(), 0, 0, 0, 0);
    dfs(board, board[0].size(), 0, 0, 1, 0);
    return result;
}

 

*3차원 bfs 풀이

map에 상태(y,x,dir)일때 비용을 기록

마찬가지로 기록된 비용보다 싼경우에만 탐색

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;
int MAP[25][25][5];  // 진행중인 방향
bool visited[25][25];
int dy[4] = {-1, 1, 0, 0};  // 상하좌우
int dx[4] = {0, 0, -1, 1};
//직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500
int solution(vector<vector<int>> board) {
    int answer = INF;
    int n = board.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < 4; k++) {
                MAP[i][j][k] = INF;
            }
        }
    }
    for (int k = 0; k < 4; k++) {
        MAP[0][0][k] = 0;
    }
    queue<pair<pair<int, int>, int>> q;
    q.push({{0, 0}, 0});
    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int dir = q.front().second;
        q.pop();
        visited[y][x] = true;
        for (int k = 0; k < 4; k++) {
            int ny = y + dy[k];
            int nx = x + dx[k];
            int ndir = k;
            if (0 > ny || ny > n - 1 || 0 > nx || nx > n - 1) continue;
            if (board[ny][nx] == 1) continue;  // 벽은 진행 불가          
            if (dir == ndir) {  // 그대로 전진
                if (MAP[ny][nx][ndir] > MAP[y][x][dir] + 100) {
                    MAP[ny][nx][ndir] = MAP[y][x][dir] + 100;
                    q.push({{ny, nx}, ndir});
                }                
            } else {  // 방향이 바뀜
                if (MAP[ny][nx][ndir] > MAP[y][x][dir] + 600) {
                    MAP[ny][nx][ndir] = MAP[y][x][dir] + 600;
                    q.push({{ny, nx}, ndir});
                } 
            }
        }
    }
    for (int i = 0; i < 4; i++) {
        answer = min(answer, MAP[n - 1][n - 1][i]);
    }
    return answer-500;
}