[카카오][BFS/DP][lv.3] 경주로 건설 - 자바(Java)

프로그래머스 > 코딩테스트 연습 > 2020 카카오 인턴십 > 경주로 건설

 

 

문제 링크

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

프로그래머스

 

 

 

 

---

 

문제

문제 설명

건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다.
제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다.
설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다.
경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1) 칸(우측 하단)입니다. 죠르디는 출발점인 (0, 0) 칸에서 출발한 자동차가 도착점인 (N-1, N-1) 칸까지 무사히 도달할 수 있게 중간에 끊기지 않도록 경주로를 건설해야 합니다.
경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있으며, 벽이 있는 칸에는 경주로를 건설할 수 없습니다.
이때, 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로 라고 합니다.
또한 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부릅니다.
건설 비용을 계산해 보니 직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 듭니다.
죠르디는 견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 합니다.

예를 들어, 아래 그림은 직선 도로 6개와 코너 4개로 구성된 임의의 경주로 예시이며, 건설 비용은 6 x 100 + 4 x 500 = 2600원 입니다.

또 다른 예로, 아래 그림은 직선 도로 4개와 코너 1개로 구성된 경주로이며, 건설 비용은 4 x 100 + 1 x 500 = 900원 입니다.

---

도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

• board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
• board 배열의 각 원소의 값은 0 또는 1 입니다.
  • 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
  • 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
• board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
• 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.

 

✅ 풀이 과정

0.  자료구조 / 알고리즘 선택

- 최소비용을 계산하는 문제

- 전체를 돌 필요가 없다!

 

>>>>  bfs

 

1. 복잡도 고려

 

최악의 케이스를 고려해봤다.

 

• 배열의 크기는 최대 25*25 = 625칸이다.
• 한번의 bfs만 호출하면 된다. (0,0) > (n-1,n-1) 
• 큐가 빌때까지 반복하고, 내부에서는 4방향 체크하는 반복이 일어나므로 정확하게는 알 수 없다.

 

 

<MinValue의 초기값 설정을 위한 연산>

눈뽕주의...ㅠㅠ

 

 

초기값을 10만으로 설정하면 20,21번 테스트케이스 통과를 못하는데 모르겠다. 

최악의 경우를 고려한다고 해도 최소값이 10만이 안넘는 것 같은데 왜 MAX_VALUE에서만 동작할까?

20번 21번 테스트케이스가 무슨 애들인지 궁금해진다

 

 

 

내생각엔 이게 최악의 케이스인데 더 최악이 있을지는 모르겠다. 

 

 

(수정  22.12.12)

 

초반에 10만이 안넘는다고 얘기한건 계산 실수다..!

내가 생각한 최악의 케이스에서 최소값은 10만이 넘는다!!!

 

아마 20 21번 TC가 worst case에 가까운 애들인가보다.

 

 

 

 

 

2. 수도코드/ 알고리즘 생각

생각을 실패해서 다른사람들의 코드를 참고하면서 공부했다. ㅋㅋㅋㅋㅋㅋㅋ 

내가 쓴 코드는 60몇점 나옴 ㅠㅠ

 

• 큐를 만든다
• 방문 처리 배열을 만든다 (2차원 배열)
• 큐에 현재 위치(row, column)와 방향(dir)에 대한 정보를 주고,
• 큐가 안비었으면 반복
  • 큐에서 맨 앞의 값을 뺀다
  • 뺀 값이 r == n-1, c == n-1이면 최소값을 찾아준다.
  • 4방향을 반복해 이동할 위치를 만든다.
    • 해당 방향 유효성 체크
  • 건설 비용 추가 (100, 600)
  • 방문 안했거나, 더 작은 값을 찾은경우엔 업데이트 해준다.
• return answer 

 

✅  초안 ) 실패코드 ...🥲🥲

엄청 많은 테스트 케이스를 틀렸다.

• 정확성: 64.0
• 합계: 64.0 / 100.0
• 틀린 TC : 4, 11, 15~20, 25

import java.util.*;
 
class Solution {
    
    int n;
    int[][] d = {{1,0},{-1,0},{0,1},{0,-1}};
    
    public int solution(int[][] board) {
        n = board.length;

        int[][] visited = new int[n][n];
        return bfs(board, visited);
    }
    
    public int bfs(int[][] board, int[][] visited) {
        int x=0, y=0, direction =-1;
        visited[y][x] = 1;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {y, x, direction});

        int result_cost=Integer.MAX_VALUE;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int r = now[0];
            int c = now[1];
            int dir = now[2];

            if(r == n-1 && c == n-1){
                result_cost = Math.min(result_cost,board[r][c]);
            }

            for (int i=0; i<4; i++) {
                int dr = r + d[i][0];
                int dc = c + d[i][1];
                int ddir = i;

                if( dr<0 || dr>=n || dc<0 || dc>=n ) {
                    continue;
                }

                if(board[dr][dc] == 1){
                    continue;
                }

                //여기까지 왔으면 이동가능한 곳이므로, 건설비용 추가
                int nextcost = 0;
                if(dir == ddir || dir == -1) nextcost = board[r][c] + 100;
                else nextcost = board[r][c] + 600;

                //방문 안한곳이거나,  움직이려는 곳의 현재 비용이. 지금 + cost보다 작으면, 비용 할당
                if(visited[dr][dc] == 0 || board[dr][dc] >= nextcost ) {
                    visited[dr][dc] = 1;
                    queue.add(new int[] {dr,dc,i});
                    board[dr][dc] = nextcost;
                }
            }
        }
        return result_cost;
    }
}

 

다른 사람들의 코드를 참고하니까 dp 테이블로 3차원배열을 만들어주는 사람이 많았다.

방향까지 고려한 최소값을 고려해줘야한다고 하는데 이유를 확실하게 모르겠다.

방향까지 고려하면 어떤 효과가 있는지 이해가 확실히 안된것 같다

일단 다른사람들 설명도 보고 이해해보자.

 

 

 

조금만 생각해보면

1) 한번만 방문하는게 아니기 떄문에 방향을 고려해야지 해당 로직이 움직일것 같긴하다

2) 그럼 위에서 방문했을떄 오른쪽 /왼쪽/아래에서 방문했을때의 최소값을 기록하는거겠지? 

3) 희승코드 참고했을 떄 방향별로 들어왔을 때는 방향별로 들어왔을 때의 최소값을 기록이 필요하다.

 

 

 

...

 

 

다른사람의 설명을 긁어왔다.

 

2개를 같이 보면 이해가 좀 되는것 같다. 

이따  내 말로 풀어서 설명을 바꿔보자..

 

 

✔️ 1번 블로그

https://heyksw.tistory.com/m/6

아래 그림을 보면서 좀더 이해해보자. 1,1로 들어가는 경우가 2가지가 있는데 어떻게 들어가는게 최소값인지

2차원배열하나로는 확인할 수 없다.

 

큐에 수많은 원소(노드)들이 담기겠지만, 다음의 두 상황을 비교해보자.

두 화살표를 고려할때 1번이 2번보다 빨리 큐에 담긴다. (상, 좌, 하, 우 의 순서로 큐를 담기 때문)

 

1번 화살표가 진행된 후, graph[1][1]=1200으로 업데이트된다. 큐에는 (1,1,3)이 담긴다. 3은 오른쪽을 의미한다.

2번 화살표가 진행된 후, graph[1][1]=700으로 업데이트된다. 큐에는 (1,1,2)가 담긴다. 2는 아래쪽을 의미한다.

 

후에, 큐에 담겼던 (1,1,3)이 처리될 것이다. 그 노드를 처리할 때, 오른쪽 (1,2)로 갈 수 있으므로 

cost = graph[x][y] + 100의 코드가 실행된다.

 

기억해보면, (1,1,3)은 (1,0)(=600)에서 3(오른쪽)으로 온 노드이다. (1,0)(=600)은 위(0,0)에서 아래(방향 2)로 온 노드 이므로, 아래쪽 -> 오른쪽으로 방향 전환이 이루어졌기 때문에 (1,1)의 값이 1200로 설정 되었었다. 

 

그러면 거기서 한번 더 같은 방향인 오른쪽(1,2)으로 가면 1200 + 100 = 1300이 되어야 할 것이다.

하지만 cost = graph[x][y] + 100이 실행되는 시점에서 graph[x][y] 는 이미 2번 화살표 때문에 700으로 변경되어있다. 이는 1300으로 이루어질 수 있는 엄청난 스노우볼의 씨앗을 틀어막는 것이다.

 

따라서 1300이 되어야 할 값이 700 + 100 = 800. 엉뚱한 값이 되는 상황이 벌어지는 것이다.

이를 방지하기 위해, graph[nx][ny]에 값을 업데이트 하는 것이 아니고 큐에 노드를 담을때마다 cost를 같이 담아야 한다.

 

 

 

 

 

 

✔️ 2번 블로그

https://sohee-dev.tistory.com/142

다음방향도 고려해야하기 때문에 3차원 배열을 쓴다.

A: 현재 900원 -> 다음이 직선 1000원 -> 다다음이 코너 1600원

B: 현재 1000원 -> 다음이 직선 1100원 -> 다다음이 직선 1200원

 

위의 경우 >>  2차원 DP를 사용하면 다음 좌표에 1000원인 경우만 가정하게 되기 때문에 다다음이 최소라고 보장할 수 없다.

 

 

 

 

 

결국 bfs를 통해 4방향을 탐색하고 방향별로 값을 저장해놔야지, 마지막에 최소값을 확신할 수 있다는의미인것 같다. (위에서 온 값이 최소일수도 왼쪽에서 온 값이 최소일수도 있으니..)

bfs의 특성상 자식을 쭉 도는 특징 떄문인가?

 

 

 역시 난 초급에서 벗어나지 못했다 ㅋㅋㅋㅋㅋㅋㅋㅋ

bfs랑 dp랑 섞이니까 못푸는거 봐라 ㅠㅠㅠㅠ휴 

좀더 공부해보고 비슷한문제를 하나 더 풀어봐야할듯 하다.

 

 

✅ 공부한 이후의 정답코드 

import java.util.*;
 
class Solution {
    
    int N;
    int [][][] visited;
    int[][] d = {{1,0},{-1,0},{0,1},{0,-1}};
    
    public int solution(int[][] board) {
        N = board.length;
        visited = new int[N][N][4];

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

        int min_cost = Integer.MAX_VALUE;

        while(!q.isEmpty()) {
            Node now = q.poll();

            if(now.r == N-1 && now.c == N-1) {
                min_cost = Math.min(min_cost,now.cost);
            }

            for(int dir=0; dir<4; dir++) {
                int dr = now.r + d[dir][0];
                int dc = now.c + d[dir][1];

                if(dr<0 || dr >= N || dc<0 || dc >= N || board[dr][dc] == 1) {
                    continue;
                }

                int nextCost = now.cost;
                if(now.dir == -1 || now.dir == dir) { 
                    //처음이라 비교대상이 없는 경우엔 무조건 100원만 추가,
                    //이전과 같은 방향인 경우에도 100원 추가
                    nextCost += 100;
                }
                else {
                    nextCost += 600;
                }

                if(visited[dr][dc][dir] == 0 || board[dr][dc] >= nextCost) {
                    q.add(new Node(dr,dc,dir,nextCost));
                    visited[dr][dc][dir] = 1;
                    board[dr][dc] = nextCost;
                }
            }
        }
        return min_cost;
    }

    public class Node {
        int r, c, dir, cost;

        public Node(int r, int c, int dir, int cost) {
            this.r = r;
            this.c = c;
            this.dir = dir;
            this.cost = cost;
        }
    }
}

 

 

 

✅ 문제를 풀기 위해 새롭게 알게된 점

• 방향까지 합친 3차원 배열을 사용한다! (메모이제이션)
  
  • 이문제에선 여러번 방문이 가능하기 때문에, 4가지 방향에서 오는 경우를 저장해주기 위함이다.
  • 공부를 더하자.. 
• node의 정보가 많으면 class 처리하는게 편하다!@
• 최소값이든 최대값 구하는 문제 나오면 그냥  Integer.MAX_VALUE같이 해당 타입의 최대/최소값을 쓰자

 

 

 

역시 난 너무 부족하다는걸 깨닫게 된 문제 ㅠㅠ

좀더 어려운문제에 많이많이 도전해야겠다!

 

---

references

프로그래머스