Programmers[62050] - 지형 이동[Level4]

링크

프로그래머스

문제설명

• 영역을 height기준으로 나눈뒤, 모든 영역을 연결할 때 필요한 cost를 구하면 된다.

문제풀이

• 영역구분(BFS,DFS)
• 영역간 이동경로 그래프(그래프)
• 영역 연결(최소 스패닝 트리-Prim)

문제코드

import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class Solution62050_지형_이동 {

    public static int[][] dir= {
            {-1,0},    
            {1,0},    
            {0,-1},    
            {0,1}    
    };

    public static int solution(int[][] land, int height) {

        int N = land.length;

//        영역 구분하기
        int[][] color = new int[N][N];
        int color_cnt=0;
        LinkedList<int[]> q;
        int[] now;
        int nr;
        int nc;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(color[i][j]==0) {
                    color_cnt++;
                    q = new LinkedList<int[]>();
                    q.add(new int[] {i,j});
                    color[i][j]=color_cnt;
                    while(!q.isEmpty()) {
                        now=q.poll();
                        for (int d = 0; d < 4; d++) {
                            nr = now[0] + dir[d][0];
                            nc = now[1] + dir[d][1];
//                            방문안했고, 이동가능(거리차이가 height이하일 때) 
                            if(nr>=0 && nr<N && nc>=0 && nc<N
                            && color[nr][nc]==0 && Math.abs(land[now[0]][now[1]]-land[nr][nc])<=height) {
                                q.add(new int[] {nr,nc});
                                color[nr][nc]=color_cnt;
                            }
                        }
                    }
                }
            }
        }

//        그래프 만들기
//        최악의 경우 color_cnt 90000임
//        90000*90000의 인접행렬을 만들 순 없음
//        인접 리스트로 구현
        HashMap<Integer, Integer>[] adj = new HashMap[color_cnt+1];
        for (int i = 1; i <= color_cnt; i++) {
            adj[i] = new HashMap<Integer, Integer>();
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int d = 0; d < 4; d++) {
                    nr = i + dir[d][0];
                    nc = j + dir[d][1];
//                    경계 안에서, 인접한 칸이 사다리로 넘어가야 할 경우(색이 다름)
                    if(nr>=0 && nr<N && nc>=0 && nc<N && color[i][j]!=color[nr][nc]) {
//                    현재 색 그룹 -> 인접 색 그룹 경로,cost 추가 or 업데이트
                        if(adj[color[i][j]].containsKey(color[nr][nc])) {
                            adj[color[i][j]].put(color[nr][nc], Math.min(adj[color[i][j]].get(color[nr][nc]),Math.abs(land[i][j]-land[nr][nc])));
                        }
                        else {
                            adj[color[i][j]].put(color[nr][nc], Math.abs(land[i][j]-land[nr][nc]));
                        }
                    }
                }
            }
        }

//        Prim
        int answer = 0;
        boolean[] visited = new boolean[color_cnt+1];
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // TODO Auto-generated method stub
                return o1[1]-o2[1];
            }
        });
//        1부터 color_cnt를 연결시켜야 함
        visited[1]=true;
        for (int key : adj[1].keySet()) {
            pq.add(new int[] {key,adj[1].get(key)});
        }

        for (int i = 1; i < color_cnt; i++) {
            for (int j = 0, pqsize = pq.size(); j < pqsize; j++) {
                now = pq.poll();
//                연결 안된 노드면
                if(!visited[now[0]]) {
                    visited[now[0]]=true;
                    answer += now[1];
                    for (int key : adj[now[0]].keySet()) {
                        pq.add(new int[] {key,adj[now[0]].get(key)});
                    }
                    break;
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[][] {
            {1, 4, 8, 10},
            {5, 5, 5, 5},
            {10, 10, 10, 10},
            {10, 10, 10, 20}
        }, 3));
        System.out.println(solution(new int[][] {
            {10, 11, 10, 11},
            {2, 21, 20, 10},
            {1, 20, 21, 11},
            {2, 1, 2, 1}
        }, 1));
    }
}

아쉬운점

• 그래프를 맨 처음에LinkedList<HashMap<Integer,Integer>>[]로 했었음.
  • LinkedList<>[]만 하던가
  • HashMap<>[]만 했어야 했음.
• 영역 연결
  • MST - Prim알고리즘 까먹었음
  • Visited 초기선정 안했음
  • Visited 업데이트 안했음

잘한점

• 영역구분
  • 굿
  • color_cnt 1부터 시작하는데 이후에 index오류 안나게 전부 고려했음
• 영역간 이동경로 그래프
  • HashMap으로 선언 잘했음
    • 여러 가능성 중 Key를 기준으로 Cost최소값 업데이트하기가 편한 자료구조
  • 공간복잡도 고려함
    • 최악의 경우 300*300개의 영역이 생길 수 있음
    • 인접행렬로 하면 90000*90000의 int 배열을 생성해야함. 터짐
    • 인접리스트로 구현해야함.
  • 양방향 그래프 고려됨
    • 사실 고민많이했었는데, N*\N에서 4방향으로 모두 간선고려하기때문에 양방향그래프를 만들 수 있음.
      • 굳이 단방향 그래프 만들려면 visitcheck하면서 간선만들면 될듯
• 영역 연결
  • Priority Queue로 Prim 구현했음
  • 경로탐색을 HashMap탐색하는 방법으로 잘 구현했음
  • HashMap Iterator쓰는법은 아직 모르겠음...