1. 문제 설명
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
아이디어는 그다지 어렵지 않은데, 객체 지향 설계 원칙 철저히 지켜가면서 풀면 무조건 메모리 초과 + 시간 초과에 발목을 잡힌다.
2. 아이디어
문제를 풀기 위해, 해결 영역을 3가지로 분리했다.
- 사다리를 설치하지 않아도 되는 영역을 SCC로 묶기 (BFS)
- 각 영역 i에서 영역 j로 이동하기 위한 최소 사다리 비용 계산
- 모든 영역을 잇기 위한 최소 사다리 설치 비용 계산 (크루스칼 알고리즘)
📌 SCC로 영역 구분
SCC라는 용어가 어려울 수 있는데, 그냥 쉽게 말해서 사다리 설치 안 하고도 이동 가능한 영역을 묶어주는 작업이다.
모든 정점을 순회하면서, bfs로 체크만 해주면 끝나는 작업.
처음에는 아래와 같이 구현했었다.
private int makeSCC(int[][] land, int height) {
Queue<Node> q = new LinkedList<>();
scc = new int[N][N];
int groupNum = 0;
for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) scc[i][j] = -1;
for (int row=0; row<N; ++row) for (int col=0; col<N; ++col) { // 모든 정점 순회
if (scc[row][col] != -1) continue; // 이미 그룹핑됐으면 패스.
q.offer(Node.of(row, col));
while (!q.isEmpty()) {
Node cur = q.poll();
scc[cur.getY()][cur.getX()] = groupNum;
for (int dir=0; dir<4; ++dir) {
int ny = cur.getY() + dydx[dir][0];
int nx = cur.getX() + dydx[dir][1];
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue; // 범위 넘어서면 패스
if (scc[ny][nx] != -1) continue; // 이미 방문한 지점 패스
if (Math.abs(land[cur.getY()][cur.getX()] - land[ny][nx]) > height) continue; // 이동 조건 벗어나면 패스
q.offer(Node.of(ny, nx));
}
}
++groupNum;
}
return groupNum - 1;
}
private static final class Node {
private final int y;
private final int x;
private Node(int y, int x) {
this.y = y;
this.x = x;
}
public static Node of(int y, int x) {
return new Node(y, x);
}
public int getY() {
return this.y;
}
public int getX() {
return this.x;
}
}
정확히 어디서 그렇게 많은 메모리를 잡아먹고 있었는지는 모르겠지만, 위 코드에서 가장 심각한 오류가 있던 건 사실이다.
1️⃣ 객체 사용 제거
// 기존: Custom Node 클래스 사용
private static final class Node {
private final int y;
private final int x;
// ... getters, factory method 등
}
// 개선: 단순 int[] 배열 사용
int[] cur = new int[]{row, col};우선 첫 번째로 Node 객체를 아예 없애버리고, 2차원 배열을 사용했다.
구체적으로 클래스의 메모리가 얼마인지는 모르겠지만, 분명한 건 int 타입 size = 2 배열보다는 클 것이라 생각한다.
그리고 Heap 영역이 아닌, Stack 영역을 사용하므로, GC의 부담을 줄일 수 있을 것이라 판단했다.
2️⃣ 큐 변경
// 기존
Queue<Node> q = new LinkedList<>();
// 개선
Deque<int[]> q = new ArrayDeque<>();LinkedList는 각 노드마다 prev, next 라는 추가 데이터를 필요로 한다.
Node를 8bytes라고 가정했을 때, 앞/뒤 노드 참조를 위한 16 bytes가 따라 붙으니, 각 요소 당 24bytes 씩이나 잡아먹는다.
또한 Node 객체를 사용해버리니, 참조 요소가 힙 메모리에 분산되면서 메모리 파편화 이슈가 생길 수 있다.
반면, ArrayDeque는 내부적으로 순환 배열을 사용하므로, 요소당 약 8byte면 충분하다.
또한, Node가 아닌 정수 배열을 사용하도록 수정했다.
이렇게 하면 연속된 메모리 블록을 사용하므로 캐시 지역성을 향상시키고, GC 부담도 줄일 수 있다.
3️⃣ Queue 삽입 후 검사 → Queue 삽입 전 검사
// 나중에 꺼냈을 때, groupNum을 매기는 방법
while (!q.isEmpty()) {
Node cur = q.poll();
scc[cur.getY()][cur.getX()] = groupNum; // 꺼냈을 때 그룹 번호 매김
for (int dir=0; dir<4; ++dir) {
// 조건 검사
q.offer(Node.of(ny, nx)); // 삽입
}
}
// 일단 방문 처리 해두고 queue 삽입
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : dydx) {
// 조건 검사
scc[ny][nx] = groupNum;
q.offer(new int[]{ny, nx});
}
}예전이었으면 이 정도는 당연한 상식 수준이었는데, 요새 문제를 많이 안 풀긴 했었나 보다.
만약 일단 큐에 삽입하자는 전략을 취하게 되면, 중복 Node 삽입 문제가 발생할 수 있다.
예를 들어, 1번 노드에서 이미 10번 노드로 갈 수 있음을 확인했었는데, 2,3,4번 노드 입장에선 10번 노드가 아직 방문처리 안 되어 있으므로, 똑같은 Node를 계속 삽입할 수 있다.
물론 결과적으로 동일한 값이 나오지만, 자칫 메모리가 폭발할 수 있으므로 순서를 반드시 잘 지켜주어야 한다.
✨ 개선된 코드
private int makeSCC(int[][] land, int height) {
Deque<int[]> q = new ArrayDeque<>(); // LinkedList 대신 ArrayDeque 사용
scc = new int[N][N];
int groupNum = 0;
for (int[] row : scc) {
Arrays.fill(row, -1);
}
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (scc[row][col] != -1) continue;
q.offer(new int[]{row, col}); // Node 객체 대신 int[] 사용
scc[row][col] = groupNum;
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : dydx) {
int ny = cur[0] + d[0];
int nx = cur[1] + d[1];
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
if (scc[ny][nx] != -1) continue;
if (Math.abs(land[cur[0]][cur[1]] - land[ny][nx]) > height) continue;
scc[ny][nx] = groupNum;
q.offer(new int[]{ny, nx});
}
}
groupNum++;
}
}
return groupNum - 1;
}
📌 각 영역 i <-> j 사다리 최소 설치 비용 계산
그룹을 묶었으므로, 이제 서로 인접한 그룹 간에 연결할 수 있는 최소 비용의 사다리를 구해야 한다.
// return: i에서 j로 이동하기 위한 다리 (이차원 배열. 이동 불가능하면 최대값 MAX_DIFF)
private int[][] connectBridge(int[][] land, int maxGroupNum) {
int[][] bridges = new int[maxGroupNum+1][maxGroupNum+1];
for (int i=0; i<maxGroupNum+1; ++i) for (int j=0; j<maxGroupNum+1; ++j) bridges[i][j] = MAX_DIFF;
for (int row=0; row<N; ++row) for (int col=0; col<N; ++col) { // 모든 정점 순회
for (int dir=0; dir<4; ++dir) {
int ny = row + dydx[dir][0], nx = col + dydx[dir][1];
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
if (scc[row][col] == scc[ny][nx]) continue; // 같은 그룹이면 패스
int minDiff = Math.min(bridges[scc[row][col]][scc[ny][nx]], Math.abs(land[row][col] - land[ny][nx]));
bridges[scc[row][col]][scc[ny][nx]] = bridges[scc[ny][nx]][scc[row][col]] = minDiff;
}
}
return bridges;
}요란하게 bfs할 이유도 없고, 각 정점을 순회하면서 인접한 node가 다른 영역에 있는지만 체크해주면 끝난다.
이게 대체 뭐하는 건가 싶을 수 있는데, i에서 j로 이동하는 최소 다리 비용을 계산해서 bridges에 넣어주는 과정이다.
예를 들어, 다음과 같은 scc를 만들었다고 하자.
| 0 | 0 | 0 | 0 |
| 1 | 2 | 2 | 0 |
| 1 | 2 | 2 | 0 |
| 1 | 1 | 1 | 1 |
그럼 bridges의 결과는 다음과 같다.
| INF | 8 | 10 |
| 8 | INF | 19 |
| 10 | 19 | INF |
설령 모든 좌표가 하나의 그룹으로 묶였다고 해도, bridges의 크기는 N*N밖에 되지 않으므로 크게 문제가 되진 않을 거라 생각한다.
그럼에도 만약 이를 개선해보고 싶다면, 다음과 같은 아이디어를 떠올려볼 수도 있다.
- 어차피 이후 최소 비용 사다리를 그리디하게 고를 거라면, 이차원 배열이 아닌 리스트 하나에 넣고 정렬을 해버려도 문제가 되지 않는다.
- i→j, j→i는 언제나 중복이고, i→i는 언제나 무의미한 값이다. 연결되지 않은 간선 정보가 필요할 일도 없으므로, 처음부터 인접 리스트로 그래프를 그리는 게 효율적이다.
ArrayList 같은 걸로 만들어서 정렬을 할 거라면 첫 번째 방법을 선택하면 되고, 나는 다른 방법으로 정렬을 진행할 생각이라 두 번째 방법으로 개선했다.
private List<Edge>[] bridges; // 인접 리스트로 변경
private void connectBridge(int[][] land, int maxGroupNum) {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) { // 모든 정점 순회
for (int[] d : dydx) {
int ny = row + d[0], nx = col + d[1];
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue; // 범위 벗어나면 제외
if (scc[row][col] == scc[ny][nx]) continue; // 같은 그룹이면 제외
int cost = Math.abs(land[row][col] - land[ny][nx]); // 사다리 설치 최소값 계산
addEdge(scc[row][col], scc[ny][nx], cost); // edge 업데이트
}
}
}
}
private void addEdge(int from, int to, int cost) {
// 이미 있는 엣지인지 확인하고 더 작은 비용으로 업데이트
for (Edge edge : bridges[from]) {
if (edge.to == to) {
edge.cost = Math.min(edge.cost, cost);
return;
}
}
bridges[from].add(new Edge(to, cost));
// bridges[to].add(new Edge(from, cost)); // 필요 없음! 어차피 중복
}
private static class Edge {
int to, cost;
int from; // from은 필요한 경우에만 사용
Edge(int to, int cost) {
this.to = to;
this.cost = cost;
}
Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
}
📌 모든 그룹을 잇는 최소 사다리 설치 비용 계산
사다리 정보는 준비가 됐는데, 최소 비용을 계산하려니 살짝 막막했었다.
그런데 그래프를 그려보면 생각보다 별 문제가 되질 않는다.
만약 위와 같이 그룹이 나뉘어져 있다면, 오른쪽처럼 트리 구조를 떠올려보면 된다.
여기서 각 그룹은 반드시 하나의 다리를 선택해야만 하지만, 아무리 복잡한 그래프를 그려도 결과는 하나의 부모를 가질 수밖에 없는 구조가 나온다.
물론 사다리는 양방향이다.
하지만 우리가 그래프를 이동하기 위한 목적이 아니라, 모든 정점을 하나로 이어주는 엣지를 찾는 것 뿐이라면 모든 엣지의 방향을 부모로 향한다는 제약을 걸어도 아무런 문제가 되질 않는다.
그리고 각 노드가 반드시 하나의 부모만을 가진다는 전제 조건이 성립한다면, Union-Find를 쉽게 떠올려 볼 수 있다.
(생각해보니 그래프를 너무 막 그려서 이해가 어려울 수도 있을 거 같은데, bfs 순서를 고려하면 상식적으로 위와 같은 그래프가 나올 수가 없다. 예를 들어, 노드5가 오직 자신보다 큰 노드 번호들과 매칭되는 경우가 존재할 수가 없다는 것이다. 직접 그려보면 왜 Union-find를 선택해도 문제가 없는 지 알 수 있다.)
문제는 사다리를 어떤 기준으로 선택해야 하냐는 것이다.
bfs? dfs? 어떻게 방문 처리를 할 것이며, 최소 다리를 판단할 것인가?
다익스트라를 쓰려고 해도, source와 dest를 무슨 수로 정할 것인가?
하지만 우리는 Edge 비용을 이미 알고 있다.
그렇다면 여기선 "그리디"하게 접근해볼 수 있다는 것이다.
👉 언제나 가장 작은 비용의 다리를 설치하는 것이 이득이다!
// 모든 정점이 연결되었을 때, 사다리가 최소가 되는 경우
// 다리는 반드시 하나를 선택해야만 함.
// 그리디: 언제나 사다리 설치 비용이 최소되는 값을 선택함.
// 연결: Union-find 연결된 노드는 같은 부모 노드를 바라봄.
private int caclMinCost(int[][] bridges, int maxGroupNum) {
List<BridgeCost> bridgeCosts = sortBridge(bridges, maxGroupNum); // bridges 비용으로 정렬
int answer = 0;
int[] nodes = new int[maxGroupNum+1];
for (int i=0; i<maxGroupNum+1; ++i) nodes[i] = i;
for (BridgeCost bridgeCost : bridgeCosts) {
if (matchParent(nodes, bridgeCost.getPre(), bridgeCost.getPos())) continue;
answer += bridgeCost.getCost();
unionParent(nodes, bridgeCost.getPre(), bridgeCost.getPos());
}
return answer;
}
private List<BridgeCost> sortBridge(int[][] bridges, int maxGroupNum) {
List<BridgeCost> result = new ArrayList<>();
for (int i=0; i<maxGroupNum+1; ++i) for (int j=i; j<maxGroupNum+1; ++j) { // 중복 제거
if (bridges[i][j] == MAX_DIFF) continue;
result.add(BridgeCost.of(bridges[i][j], i, j));
}
Collections.sort(result);
return result;
}
private static final class BridgeCost implements Comparable<BridgeCost> {
private final int cost;
private final int pre;
private final int pos;
private BridgeCost(int cost, int pre, int pos) {
this.cost = cost;
this.pre = pre;
this.pos = pos;
}
private static BridgeCost of(int cost, int pre, int pos) {
return new BridgeCost(cost, pre, pos);
}
public int getCost() {
return this.cost;
}
public int getPre() {
return this.pre;
}
public int getPos() {
return this.pos;
}
@Override
public int compareTo(BridgeCost o) {
return this.cost - o.getCost();
}
}처음에는 위와 같이 구현했는데, 이렇게 할 거였으면 bridges라는 2차원 배열을 만들 의미가 없다.
그래서 (2)에서 개선된 방법에 이어서 진행한다면, 우선 순위 큐에 넣어주면 어차피 알아서 정렬해준다.
private int calcMinCost(int maxGroupNum) {
nodes = new int[maxGroupNum + 1];
for (int i = 0; i <= maxGroupNum; i++) {
nodes[i] = i;
}
// 모든 엣지를 비용순으로 정렬
PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);
for (int i = 0; i <= maxGroupNum; i++) {
for (Edge edge : bridges[i]) {
pq.offer(new Edge(i, edge.to, edge.cost));
}
}
int answer = 0;
while (!pq.isEmpty()) {
Edge edge = pq.poll();
if (!matchParent(edge.from, edge.to)) {
answer += edge.cost;
unionParent(edge.from, edge.to);
}
}
return answer;
}
코테 감이 많이 녹슬기도 했고, 보통 Java는 애플리케이션 개발할 때나 썼지 코테 전용으로 잘 안 써봐서
메모리 절약하는 방법이 여전히 익숙하질 않다.
보통 개발할 때는 메모리를 희생해서라도, 깔끔한 코드를 유지하는 것을 중요하게 여기는 반면
코테는 흑마법을 써서라도 시간/공간 복잡도를 줄여야 하다보니..
문제는 요샌 구현 문제를 많이 출제하는 경향이 있고, 코드를 어떻게 작성했냐를 더 중요시 여기는 곳이 많아졌다는데
대체 뭐 어느 기준에 맞추라는 건지 모르겠다.
3. 코드
import java.util.*;
class Solution {
private static final int MAX_DIFF = 50000;
private int N = 0;
private static final int[][] dydx = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private int[][] scc;
private List<Edge>[] bridges; // 인접 리스트로 변경
private int[] nodes;
// land[i][j]: (i, j)의 높이 (1 <= H <= 10,000)
// 4 <= N <= 300
// 이동 조건: |현재 칸 - 이동 칸| <= height
// 만약 |현재 칸 - 이동 칸| > height면, 사다리 설치 -> 설치 비용 = |현재 칸 - 이동 칸|
// 반환 값: 사다리 설치 비용 최소화
//
// (1) bfs -> 모든 정점에서 시작해서 bfs? 사다리 재활용은?
// (2) 이동 가능한 그룹 묶기? -> 인접한 그룹은 어떻게 판단? 그룹 사이 최소 사다리 비용은 어떻게 판단? 다른 그룹과 연결되어 있다면?
// 아이디어 (SCC)
// - 사다리 설치 없이 이동 가능한 구역 묶기. (bfs)
// - 구역 간에 사다리 최소 설치 비용 탐색
// - ex. 1<->2 (5), 2<->3(10), 1<->3(-1) (단, -1은 이동 불가) ==> 최소 비용 15
// - ex. 1<->2 (8), 2<->3(19), 1<->3(10) => 최소 비용 1<->2 && 1<->3 (18)
public int solution(int[][] land, int height) {
N = land.length;
int maxGroupNum = makeSCC(land, height);
if (maxGroupNum == 0) return 0;
// 인접 리스트 초기화
bridges = new List[maxGroupNum + 1];
for (int i = 0; i <= maxGroupNum; i++) {
bridges[i] = new ArrayList<>();
}
connectBridge(land, maxGroupNum);
return calcMinCost(maxGroupNum);
}
private int makeSCC(int[][] land, int height) {
Deque<int[]> q = new ArrayDeque<>(); // LinkedList 대신 ArrayDeque 사용
scc = new int[N][N];
int groupNum = 0;
for (int[] row : scc) {
Arrays.fill(row, -1);
}
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (scc[row][col] != -1) continue;
q.offer(new int[]{row, col}); // Node 객체 대신 int[] 사용
scc[row][col] = groupNum;
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : dydx) {
int ny = cur[0] + d[0];
int nx = cur[1] + d[1];
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
if (scc[ny][nx] != -1) continue;
if (Math.abs(land[cur[0]][cur[1]] - land[ny][nx]) > height) continue;
scc[ny][nx] = groupNum;
q.offer(new int[]{ny, nx});
}
}
groupNum++;
}
}
return groupNum - 1;
}
private void connectBridge(int[][] land, int maxGroupNum) {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
for (int[] d : dydx) {
int ny = row + d[0], nx = col + d[1];
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
if (scc[row][col] == scc[ny][nx]) continue;
int cost = Math.abs(land[row][col] - land[ny][nx]);
addEdge(scc[row][col], scc[ny][nx], cost);
}
}
}
}
private void addEdge(int from, int to, int cost) {
// 이미 있는 엣지인지 확인하고 더 작은 비용으로 업데이트
for (Edge edge : bridges[from]) {
if (edge.to == to) {
edge.cost = Math.min(edge.cost, cost);
return;
}
}
bridges[from].add(new Edge(to, cost));
}
private int calcMinCost(int maxGroupNum) {
nodes = new int[maxGroupNum + 1];
for (int i = 0; i <= maxGroupNum; i++) {
nodes[i] = i;
}
// 모든 엣지를 비용순으로 정렬
PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);
for (int i = 0; i <= maxGroupNum; i++) {
for (Edge edge : bridges[i]) {
pq.offer(new Edge(i, edge.to, edge.cost));
}
}
int answer = 0;
while (!pq.isEmpty()) {
Edge edge = pq.poll();
if (!matchParent(edge.from, edge.to)) {
answer += edge.cost;
unionParent(edge.from, edge.to);
}
}
return answer;
}
private boolean matchParent(int a, int b) {
return findParent(a) == findParent(b);
}
private void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) nodes[b] = a;
else nodes[a] = b;
}
private int findParent(int cur) {
if (nodes[cur] == cur) return cur;
return nodes[cur] = findParent(nodes[cur]);
}
private static class Edge {
int to, cost;
int from; // from은 필요한 경우에만 사용
Edge(int to, int cost) {
this.to = to;
this.cost = cost;
}
Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
}
}