지형 이동

2025-05-09

#JAVA#프로그래머스

4분

문제 링크

문제 풀이 시간 : 1시간

문제 요약

•
N x N 크기의 격자 지형이 주어짐. 각 칸은 높이를 나타내는 숫자를 가짐

•
상, 하, 좌, 우로 이동 가능하며, 인접 칸의 높이 차가 height 이하일 경우 사다리 없이 이동 가능

•
높이 차가 height를 초과하면 사다리를 설치해야 하며, 비용은 두 칸의 높이 차와 같음

•
목표: 모든 칸을 방문하기 위해 설치해야 하는 사다리 비용의 최소값을 구함

•
사다리 설치 개수에는 제한이 없음

문제 풀이

문제를 읽고 바로 일단 각 영역을 분류를 해야겠다는 생각을 했다.

영역을 분류하기 위해 각 칸을 bfs로 돌면서 높이 차가 height 이하인 경우를 다 합쳐주면서

map 배열에 저장했다.

영역 분류 코드

Java

public void find(int x, int y, int num) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x, y));
        map[x][y] = num;

        while(!q.isEmpty()) {
            Node now = q.poll();
            for(int i = 0; i < 4; i++) {
		            // 각 칸에 대해 주위 탐색
                int tx = now.x + dir[i][0];
                int ty = now.y + dir[i][1];
                
                //격자를 넘어가는지
                if(!check(tx, ty))
                 continue;
                //이미 영역이 있다면 넘어감
                if(map[tx][ty] != 0) 
	                continue;
	                
	              //두 칸의 차이가 최대 높이차보다 크다면 다른 영역
                if(Math.abs(LAND[now.x][now.y] - LAND[tx][ty]) > HEIGHT) 
	                continue;
	              //영역 표시
                map[tx][ty] = num;
                q.add(new Node(tx, ty));
            }
        }
    }

다음으로 분류된 영역들이 만나는 부분을 찾아 연결을 해줘야 한다.

우리는 최소의 값으로 사다리를 연결해야 하기 때문에 각 영역들의 연결에 대해 가장 작은 값만 맵에 저장해준다.

예를 들어 2,3 영역이 연결된 부분의 가중치가 5, 7, 9 가 있다면 이 중에서 5의 가중치만 저장해 주는 것이다.

영역 간 최소 높이 저장 코드

Java

Map<String, Integer> edgeMap = new HashMap<>();
for(int i = 0; i < max_x; i++) {
    for(int j = 0; j < max_y; j++) {
        for(int k = 0; k < 4; k++) {
		        //각 칸에 대해 주변 탐색
            int tx = i + dir[k][0];
            int ty = j + dir[k][1];
            
            //격자를 넘어가는지
            if(!check(tx, ty)) 
                continue;
            
            //현재 위치의 영역 번호
            int from = map[i][j];
            //주위 칸의 영역 번호
            int to = map[tx][ty];
            
            //두 칸의 영역이 같다면 넘어감
            if(from == to) 
                continue;
            
            //두 영역 사이의 가중치 구함
            int cost = Math.abs(LAND[i][j] - LAND[tx][ty]);
            
            //맵에 낮은 영역 번호, 높은 영역 번호 순으로 통일 시키기 위한 정리
            if(from > to) { 
                int tmp = from; 
                from = to; 
                to = tmp; 
            }
            
            //두 영역을 이용해 key 생성
            String key = from + "," + to;
            //맵에 최솟값만 저장함
            edgeMap.put(key, Math.min(edgeMap.getOrDefault(key, Integer.MAX_VALUE), cost));
        }
    }
}

다음으로는 이렇게 맵에 저장된 영역 간의 최소 높이차를 이용해서 연결을 해줘야 한다.

나는 연결을 위해서 union-find를 사용했는데,

union-find를 하기 위해 먼저 우선순위 큐에 위의 값들을 넣어주었다.

우선순위 큐 저장 코드

Java

PriorityQueue<Bridge> pq = new PriorityQueue<>((a, b) -> a.len - b.len);

for(Map.Entry<String, Integer> entry : edgeMap.entrySet()) {
    String[] parts = entry.getKey().split(",");
    int from = Integer.parseInt(parts[0]);
    int to = Integer.parseInt(parts[1]);
    pq.add(new Bridge(from, to, entry.getValue()));
}

우선순위 큐에 넣은 값들을 이용해 이제 최소 높이 차인 값들을 꺼내오면서 모든 영역이 연결될 때까지 연결해주면 된다.

영역 연결 코드

Union-Find 코드

Java

public int findParent(int x) {
	if(uf[x] != x) uf[x] = findParent(uf[x]);
	return uf[x];
}

public void union(int x, int y) {
	int px = findParent(x);
	int py = findParent(y);
	if(px != py) uf[py] = px;
}

영역 연결 코드

Java

// 각 영역의 부모를 저장하기 위한 배열
uf = new int[num];
//초기의 각 영역의 부모는 자기 자신
for(int i = 0; i < num; i++) 
	uf[i] = i;

while(!pq.isEmpty()) {
	Bridge now = pq.poll();
	//서로의 부모가 다르면 아직 연결되지 않은 영역들이기 때문에 연결
	if(findParent(now.from) != findParent(now.to)) {
		union(now.from, now.to);
		answer += now.len; //연결을 위해 사다리를 놓은 높이 저장
	}
}

최종 코드

Java

import java.util.*;

class Solution {
    public int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
    public int[][] LAND, map;
    public int[] uf;
    public int HEIGHT;
    public int max_x, max_y;

    public class Node {
        int x, y;
        public Node(int x, int y) { this.x = x; this.y = y; }
    }

    public class Bridge {
        int from, to, len;
        public Bridge(int from, int to, int len) {
            this.from = from;
            this.to = to;
            this.len = len;
        }
    }

    public boolean check(int x, int y) {
        return !(x < 0 || x >= max_x || y < 0 || y >= max_y);
    }

    public void find(int x, int y, int num) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x, y));
        map[x][y] = num;

        while(!q.isEmpty()) {
            Node now = q.poll();
            for(int i = 0; i < 4; i++) {
                int tx = now.x + dir[i][0];
                int ty = now.y + dir[i][1];
                if(!check(tx, ty)) continue;
                if(map[tx][ty] != 0) continue;
                if(Math.abs(LAND[now.x][now.y] - LAND[tx][ty]) > HEIGHT) continue;
                map[tx][ty] = num;
                q.add(new Node(tx, ty));
            }
        }
    }

    public int findParent(int x) {
        if(uf[x] != x) uf[x] = findParent(uf[x]);
        return uf[x];
    }

    public void union(int x, int y) {
        int px = findParent(x);
        int py = findParent(y);
        if(px != py) uf[py] = px;
    }

    public int solution(int[][] land, int height) {
        int answer = 0;
        LAND = land;
        HEIGHT = height;
        max_x = land.length;
        max_y = land[0].length;
        map = new int[max_x][max_y];

        int num = 1;
        for(int i = 0; i < max_x; i++) {
            for(int j = 0; j < max_y; j++) {
                if(map[i][j] == 0) find(i, j, num++);
            }
        }

        Map<String, Integer> edgeMap = new HashMap<>();
        for(int i = 0; i < max_x; i++) {
            for(int j = 0; j < max_y; j++) {
                for(int k = 0; k < 4; k++) {
                    int tx = i + dir[k][0];
                    int ty = j + dir[k][1];
                    
                    if(!check(tx, ty)) 
	                    continue;
	                    
                    int from = map[i][j];
                    int to = map[tx][ty];
                    
                    if(from == to) 
	                    continue;
	                    
                    int cost = Math.abs(LAND[i][j] - LAND[tx][ty]);
                    
                    if(from > to){ 
	                    int tmp = from; from = to; to = tmp; 
	                  }
	                  
                    String key = from + "," + to;
                    edgeMap.put(key, Math.min(edgeMap.getOrDefault(key, Integer.MAX_VALUE), cost));
                }
            }
        }

        PriorityQueue<Bridge> pq = new PriorityQueue<>((a, b) -> a.len - b.len);
        for(Map.Entry<String, Integer> entry : edgeMap.entrySet()) {
            String[] parts = entry.getKey().split(",");
            int from = Integer.parseInt(parts[0]);
            int to = Integer.parseInt(parts[1]);
            pq.add(new Bridge(from, to, entry.getValue()));
        }

        uf = new int[num];
        for(int i = 0; i < num; i++) uf[i] = i;

        while(!pq.isEmpty()) {
            Bridge now = pq.poll();
            if(findParent(now.from) != findParent(now.to)) {
                union(now.from, now.to);
                answer += now.len;
            }
        }

        return answer;
    }
}