[JAVA] 프로그래머스 지형이동

🤔 풀기 전의 문제에 대한 생각

☑️ 문제를 읽으며

뭔가 BFS에서는 이런 문제 유형이 따로 있지 않을까 생각이 든다..

기본 상황

모든 칸을 방문 상 하 좌 우 한칸씩 -> 칸의 높이차가 Height 이하 Height보다 많이 나면 사다리 설치 => 비용 : 높이 차만큼 최소 비용 -> BFS 사다리 갯수 제한 x 철거도 x 재사용이 가능하지 않을까? 어딘 가를 갈때 다른 곳을 경우해서 가능한 곳이면 사다리 안써도 된다.

우선 처음에 BFS 를 해서 사다리를 쓰지 않고 방문 가능한 곳 찾기.

그 후 사다리를 이용해서 가능한 곳을 찾아야 되지 않나.

문제 풀이

1 . cost 로 오름차순 정렬→ 이거 시도 중 (메모리터짐)

1. cost로 오름차순 정렬해서 방문할 순서를 정한다
   1. 즉 cost가 작은 것부터 우선순위 큐에서 뽑아서 방문을 시작할 노드로 선정
   2. 이때 색깔 처럼 숫자를 부여해서 사다리 없이 방문 가능한 것을 표현
2. 이 다음 방문이 다 끝나면 색이 다른 것끼리 높이 차를 최소로 이동할 수 있는 길 찾기
   1. 다시 BFS를 해서 다른 색으로 가는 최소를 찾아야 된다…
   2. 어떻게 구현할까?
3. 그냥 1,1 좌표를 기준으로 시작한다.→ 새로운 방문 배열
   1. 근데 이러면 다른 좌표로 시작 했을 때 더 작은 비용으로 이동 할 수 있는 길이 있지 않을까?
   2. BFS를 하면서 같은 색은 넘어가고 다른 색일 경우 class로 좌표와 cost를 저장한다.
   3. minCost값을 기준으로 사다리를 놓고, 사다리 배열을 만들어서 사다리 위치를 표현.
      1. 추후에 사다리 위치는 중복 사용 가능하게 한다.

결국 틀렸다. 이런식으로 구현하는게 아닌 것같다.

아니면 구현이 틀렸던가

Chat gpt 질문

내가 푼 풀이로 풀이 가능한지 질문

→ 가능하다

코드에서 2가지 설명

🧶 예상 시간 복잡도

✅ 코드

내 방식 코드

import java.util.*;

class Solution {
    class Position {
        int x, y, cost;
        public Position(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public int solution(int[][] land, int height) {
        int N = land.length;
        int[][] firstVisited = new int[N][N]; // 방문 및 그룹 번호 저장
        int color = 0;
        
        Queue<Position> q = new LinkedList<>();
        List<Position> edges = new ArrayList<>();
        
        // **1️⃣ BFS로 그룹 색칠**
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (firstVisited[i][j] == 0) { // 방문하지 않은 곳이면 BFS 시작
                    color++;
                    q.add(new Position(i, j, land[i][j]));
                    firstVisited[i][j] = color;
                    
                    while (!q.isEmpty()) {
                        Position cur = q.poll();
                        for (int dir = 0; dir < 4; dir++) {
                            int nx = cur.x + dx[dir];
                            int ny = cur.y + dy[dir];
                            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                            if (firstVisited[nx][ny] > 0) continue; // 이미 방문한 곳
                            
                            if (Math.abs(land[nx][ny] - cur.cost) <= height) { // 이동 가능
                                firstVisited[nx][ny] = color;
                                q.add(new Position(nx, ny, land[nx][ny]));
                            }
                        }
                    }
                }
            }
        }

        // **2️⃣ 그룹 간 최소 비용 사다리 계산**
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int dir = 0; dir < 4; dir++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                    
                    if (firstVisited[i][j] != firstVisited[nx][ny]) { // 다른 그룹 간 연결
                        int cost = Math.abs(land[i][j] - land[nx][ny]);
                        edges.add(new Position(firstVisited[i][j], firstVisited[nx][ny], cost));
                    }
                }
            }
        }

        // **3️⃣ Kruskal 알고리즘 (최소 신장 트리) 적용**
        Collections.sort(edges, Comparator.comparingInt(e -> e.cost)); // 비용 순으로 정렬
        int[] parent = new int[color + 1]; // 그룹 parent 배열
        for (int i = 1; i <= color; i++) parent[i] = i;

        int mstCost = 0, edgeCount = 0;
        for (Position edge : edges) {
            if (union(edge.x, edge.y, parent)) {
                mstCost += edge.cost;
                edgeCount++;
                if (edgeCount == color - 1) break; // MST 완성
            }
        }

        return mstCost;
    }

    private int find(int x, int[] parent) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x], parent);
    }

    private boolean union(int x, int y, int[] parent) {
        int rootX = find(x, parent);
        int rootY = find(y, parent);
        if (rootX == rootY) return false;
        parent[rootY] = rootX;
        return true;
    }
}

다른 답변

import java.util.*;

class Solution {
    class Node implements Comparable<Node> {
        int X,Y;
        int cost;
        public Node(int X,int Y,int cost){
            this.X = X;
            this.Y = Y;
            this.cost = cost;
        }
        @Override
        public int compareTo(Node other){
            return Integer.compare(this.cost,other.cost);
        }
    }
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    
    public int solution(int[][] land, int height) {
        int answer = 0;
        int N = land.length;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[][] visited = new boolean[N][N];
        
        pq.add(new Node(0,0,0));
        
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (visited[cur.X][cur.Y]) continue;
            visited[cur.X][cur.Y] = true;
            answer+= cur.cost;
            
            for (int dir = 0; dir < 4; dir ++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if (nx <0 || ny < 0 || nx>= N || ny>=N) continue;
                if (visited[nx][ny]) continue;
                int temp = Math.abs(land[cur.X][cur.Y] - land[nx][ny]);
                int newCost = temp > height ? temp : 0 ;
                pq.add(new Node(nx,ny,newCost));
            }
        }
        
        // height이하이면 비용을 0으로 설정
        return answer;
    }
}

📔 설명 및 정리

💡 설명

내 방식은 결국 BFS를 먼저 한번 시도해서 서로 다른 그룹의 트리들을 만들고

그 트리들을 하나의 최소신장트리로 구성하는 것이다.

내 방식

1. BFS로 색이 다른 그룹을 만든다.
   1. 여기서 그룹은 사다리를 타지 않고 이동 가능한 그룹이다.
   2. 각 색들을 정리하는 배열을 만든다.
2. 서로 다른 그룹 (색)을 연결하는 간선을 저장한다.
   1. 우선순위 큐나 정렬을 사용해서 크루스칼을 사용하기 위해서 오름차순 정렬
3. 크루스칼을 사용해서 MST를 구성한다.
   1. 간선을 최소비용 기준으로 선택
   2. 서로 다른 그룹인지 확인
   3. 다른 그룹이면 합치기
   4. 간선이 N-1 색의 갯수가 노드라고 치면 노드 - 1 일때까지

다른 방식 - 훨씬 간단

에초에 사다리를 놓는 것만 비용을 주고 나머지 같은 그룹은 비용을 0을 준다.

우선순위 큐로 구현하면 같은 그룹이 우선적으로 방문된다.

(비용이 0이기에 )

비용이 0인 모든 같은 그룹간 방문이 끝나고 다른 그룹과 연결되는 비용중 가장 작은 비용이 택해진다.

어찌보면 가장 간단하면서도 이게 맞다.

나는 너무 나눠서 복잡하게 생각했던것 같다.

❗ 구현 시 특이 사항

🛑 오답 코드

import java.util.*;

class Solution {
    class Position implements Comparable<Position>{
        int X,Y;
        int cost;
        
        public Position (int X,int Y,int cost){
            this.X = X;
            this.Y = Y;
            this.cost = cost;
        } 
        @Override
        public int compareTo(Position other){
            return Integer.compare(this.cost,other.cost);
        }
    }
    // BFS 
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    
    public int solution(int[][] land, int height) {
        int answer = 0;
        int N = land.length; 
        int[][] firstVisited = new int[N][N];
        
        ArrayDeque<Position> q = new ArrayDeque<>();
        ArrayDeque<Position> fq = new ArrayDeque<>();
        
        int color = 0;
        for (int i = 0 ; i < N; i ++){
            for (int j = 0 ; j < N; j++){
                if (firstVisited[i][j] == 0){
                    q.add(new Position(i,j,land[i][j]));
                    fq.add(new Position(i,j,land[i][j]));
                    
                    color++;
                    firstVisited[i][j] = color;
                    
                    while (!q.isEmpty()) {
                        Position cur = q.poll();
                        // 0보다 크다는 것은 방문했다는 것
                        for (int dir = 0 ; dir < 4; dir++) {
                            int nx = cur.X + dx[dir];
                            int ny = cur.Y + dy[dir];
                            if ( nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                            // 높이보다 크다면 방문 x or 이미 방문했으면 x 
                            if (Math.abs(land[nx][ny] - cur.cost) > height 
                                || firstVisited[nx][ny] > 0 ) 
                                continue;
                            firstVisited[nx][ny] = color;
                            q.add(new Position(nx,ny,land[nx][ny]));
                        }
                    }
                } 
            }
        }
        // 1,1 좌표를 기준으로 다시 BFS 시작 
        // 색이 다를 경우 비용
        int[][] ladder = new int[N][N];
        // 각 색별로 저장해논 것을 기준으로 뽑아서 
        while (!fq.isEmpty()) {
            Position cur = fq.poll();
            ArrayDeque<Position> qq = new ArrayDeque<>();
            PriorityQueue<Position> pq = new PriorityQueue<>();
            qq.add(cur);
            
            while (!qq.isEmpty()) {
                Position search = qq.poll();
                // 상하좌우 이동할 때 색이 다르면 pq에 추가 
                for (int dir = 0 ; dir < 4; dir++){
                    int nx = search.X + dx[dir];
                    int ny = search.Y + dy[dir];
                    if ( nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                    if (firstVisited[nx][ny] == firstVisited[search.X][search.Y]){
                        qq.add(new Position(nx,ny,0));
                    } else {
                        pq.add(new Position(nx,ny,Math.abs(search.cost - land[nx][ny])));
                    }
                    
                }
            }
            Position lad = pq.poll();
            ladder[lad.X][lad.Y] = 1;
        }
        
        for (int i = 0 ; i < N ; i++){
            System.out.println(Arrays.toString(firstVisited[i]));
        }
        for (int i = 0 ; i < N ; i++){
            System.out.println(Arrays.toString(ladder[i]));
        }
        
        
        return answer;
    }
}

메모리가 터졌다.