[프로그래머스/그래프/Lv3] 퍼즐조각 채우기 | 섬 연결하기
문제 정보
[프로그래머스/lv3] 퍼즐 조각 채우기
game_board의 빈 공간(0)과 table의 퍼즐 조각(1)을 비교하여 딱 맞게 채울 수 있는 조각의 칸 수를 구하는 구현 문제이다. 퍼즐 조각은 회전이 가능하지만 뒤집기는 불가능하며, 빈 공간보다 작거나 크면 사용할 수 없다.
제약 조건
- game_board와 table의 크기 : 1 ~ 50
- game_board와 table은 0과 1로만 구성
- 퍼즐 조각은 90도 단위로 회전 가능, 뒤집기 불가
- 빈 공간에 딱 맞아야 하며 남거나 모자라면 사용 불가
풀이
DFS인척을 하는 구현 문제로써 구현해야할 로직들이 꽤 있는 편이기에 천천히 task를 나누어 푸는게 유리한 문제이다.
크게 task를 나누면 아래 3단계로 나눌 수 있다.
1. 덩어리 추출 (BFS/DFS)
game_board에서 0으로 연결된 덩어리 → 빈 공간 목록
table에서 1으로 연결된 덩어리 → 퍼즐 조각 목록
2. 정규화
추출한 좌표들을 (0, 0) 기준으로 이동 이후 비교를 위한 정렬 처리
3. 매칭
game_board 빈 공간 하나씩 순회
각 table 조각을 4방향 회전 + 정규화 하며 비교
일치하면 answer += 조각 크기, 해당 조각 제거
구현
1. 덩어리 추출
그래프 문제로써 DFS를 활용해 덩어리를 추출한다.
코드의 재사용성을 높이기 위해 target 변수를 사용하여 game_board와 table 모두에서 사용할 수 있게 설정하였다.
좌표와 조각들을 별도의 class인 Diagram, Coordinates로 분리하였다.
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public Diagram DFS(int[][] map, int a, int b, boolean[][] visited, int target) {
Diagram diagram = new Diagram();
Queue<Coordinates> queue = new LinkedList<>();
int[] DY = {-1, 0, 1, 0};
int[] DX = {0, 1, 0, -1};
queue.offer(new Coordinates(a, b));
visited[a][b] = true;
while (!queue.isEmpty()) {
Coordinates coordinates = queue.poll();
diagram.lists.add(coordinates);
for (int i = 0; i < 4; i++) {
int y = DY[i] + coordinates.y; int x = DX[i] + coordinates.x;
if (y >= map.length || x >= map[0].length || y < 0 || x < 0 || visited[y][x] || map[y][x] != target)
continue;
visited[y][x] = true;
Coordinates move = new Coordinates(y, x);
queue.offer(move);
}
}
return diagram;
}
2. 정규화
덩어리 추출은 하였더라도 이걸 비교하는것에 대해 생각을 하게 되었는데, 크기는 내가 선택한 방법은 0,0을 기준으로 비교하고 어떤 도형을 비교할지는 같은 조건을 통해 List들을 정렬하는 방식을 택했다.
이때 적절한 정렬 및 비교를 위해 Comaparable 사용하였다.
Coordinate
1
2
3
4
5
6
7
8
9
10
11
12
class Coordinates implements Comparable<Coordinates>{
int y, x;
(...)
@Override
public int compareTo(Coordinates o) {
if (o.y == this.y)
return this.x - o.x;
return this.y - o.y;
}
}
Diagram
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Diagram {
List<Coordinates> lists = new ArrayList<>();
(...)
public boolean equals(Object o) {
Diagram diagram = (Diagram) o;
List<Coordinates> tagetList = diagram.lists;
if (tagetList.size() != lists.size())
return false;
for (int i = 0; i < tagetList.size(); i++) {
Coordinates coordinates = lists.get(i);
Coordinates compareCoordinates = tagetList.get(i);
if (coordinates.y == compareCoordinates.y && coordinates.x == compareCoordinates.x)
continue;
return false;
}
return true;
}
}
도형 정규화
Diagram 내부 함수로써 좌표(Coordinate)의 List를 가지고 있는 lists를 y 좌표 기준으로 정렬한다.
이로써 모든 도형들은 같은 조건을 가지고 정렬할 수 있다.
y, x 위치도 정렬하기 위해선 List내 가장 낮은 y, x를 기준으로 모든 도형들을 이동시켜야하는데 y 좌표는 이미 정렬된 List의 첫번째 요소를 사용한다.
x의 경우는 별도로 추출하기 위해 Stream을 사용하였다.
1
int x = lists.stream().mapToInt(c -> c.x).min().getAsInt();
stream(): 스트림을 사용하겠다.mapToInt(c -> c.x): 요소들 중x좌표만 사용.min(): 최소값을 추출.getAsInt(): Int로 return
정규화 전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
public void normalization() {
Collections.sort(lists);
Coordinates coordinates = lists.get(0);
int y = coordinates.y;
int x = lists.stream().mapToInt(c -> c.x).min().getAsInt();
for (Coordinates c : lists) {
c.y = c.y - y; c.x = c.x - x;
}
}
이 로직을 통해 같은 좌표, 같은 조건으로 정렬된 List들을 얻게 된다.
좌표, 같은 조건으로 정렬된 List들을 얻게 된다.
3. 매칭
game_board의 Diagram을 기준으로 매칭을 시작한다. 단, board의 경우 회전이 가능하기에 하나의 board의 Diagram에 대해 90도 회전을 실시한다.
좌표 내에서 회전의 경우 아래 공식을 사용하면 된다.
1
(x, y) ---> (y, -x) # 90도 회전
일시적으로 음수가 나올 수 있지만 이 경우 정규화를 통해
c.y = c.y - y; c.x = c.x - x;식을 계산하며-가 상쇄되어 다시 양수로 변환된다!
1
2
3
4
5
6
7
8
9
public Diagram rotate() {
Diagram rotateDiagram = new Diagram();
for (Coordinates c : lists) {
rotateDiagram.lists.add(new Coordinates(c.x, -c.y));
}
return rotateDiagram;
}
Iterator를 통해 하나의 Diagram에 대해 4방향을 회전과 후 정규화를 톨해 equals()를 통해 비교를 진행한다. 진행 중 같은 조각을 발견시 iter.remove()를 통해 안전한 순회 삭제 후 loop를 break 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
loop:
while (iterator.hasNext()) {
Diagram tableD = iterator.next();
// 4방향 회전하며 비교
for (int i = 0; i < 4; i++) {
tableD = tableD.rotate();
tableD.normalization();
if (tableD.equals(diagram)) {
answer += tableD.lists.size();
iterator.remove();
break loop;
}
}
이를 통해 매칭된 lists.size()를 통해 얼마나 game_board를 채울 수 있을지 알 수 있다.
문제 정보
n개의 섬이 있고, 각 섬 사이를 잇는 다리 비용이 주어진다. 모든 섬이 서로 연결되도록 다리를 건설할 때, 건설 비용의 합이 최소가 되도록 하는 값을 구하는 것이다. 단, 다리는 양방향으로 이동 가능하며, 직접 연결되지 않아도 다른 섬을 거쳐 연결되면 된다.
풀이 핵심
모든 노드를 최소 비용으로 연결하는 MST(최소 신장 트리) 문제다.
MST 문제의 경우 두 가지 풀이 방법이 있는데 두 방법 모두 풀어 보겠다.
프림(Prim) 알고리즘 풀이
프림은 Greedy 한 알고리즘으로 n이라는 섬으로 가기 위해 가장 낮은 비용을 지불 할 수 있는 경로를 찾는다.
한번 경로가 확정된 Node는 건드리지 않으며, 확정 Node와 연관된 다른 Node들 중에서 또 다시 가장 낮은 경로와 목적지를 찾아 이 과정을 반복한다.
구현에 있어서 Graph를 표현하기 위해 이중 List 배열인 List<List<int[]» graph를 사용하였다. 섬과의 연결은 양방향이기에 costs 배열에서 추출한 양쪽 값을 세팅해주었다.
1
2
3
// start node를 기점으로 end에 value만큼 추가
graph.get(start).add(new int[] {end, value});
graph.get(end).add(new int[]{start, value});
또한 가장 낮은 섬과 비용을 찾기 위해 PriorityQueue를 사용하여 경로를 관리하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
PriorityQueue<int[]> pq = new PriorityQueue<>( (a, b) -> a[1] - b[1]);
pq.offer(new int[] {0, 0});
while (!pq.isEmpty()) {
int[] node = pq.poll();
int dest = node[0]; int cost = node[1];
if (visited[dest])
continue;
visited[dest] = true;
ans += cost;
for (int[] next : graph.get(dest)) {
pq.offer(next);
}
}
Prim 전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;
public class Solution {
public int solution(int n, int[][] costs) {
int ans = 0;
List<List<int[]>> graph = new ArrayList<>();
PriorityQueue<int[]> pq = new PriorityQueue<>( (a, b) -> a[1] - b[1]);
boolean[] visited = new boolean[n];
// 초기 start 섬 설정
for (int i = 0; i < n; i++)
graph.add(new ArrayList<int[]>());
for (int i = 0; i < costs.length; i++) {
int start = costs[i][0];
int end = costs[i][1];
int value = costs[i][2];
// start node를 기점으로 end에 value만큼 추가
graph.get(start).add(new int[] {end, value});
graph.get(end).add(new int[]{start, value});
}
pq.offer(new int[] {0, 0});
while (!pq.isEmpty()) {
int[] node = pq.poll();
int dest = node[0]; int cost = node[1];
if (visited[dest])
continue;
visited[dest] = true;
ans += cost;
for (int[] next : graph.get(dest)) {
pq.offer(next);
}
}
return ans;
}
}
크루스칼 알고리즘(Kruskal Algorithm) 풀이
Graph를 그리는 프림과 달리 크루스칼은 훨씬 간단하게 구현할 수 있는데, 가장 낮은 간선을 선택하고 그 간선을 선택했을 때 Cycle이 형성되는지 확인을 반복하는 방식이다. 가장 낮은 간선의 경우 제공되는 costs 자체를 value 기준으로 정렬하고. 싸이클의 경우 union-find 알고리즘을 사용하여 판별한다.
값 기준 정렬과 싸이클 판별
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 값 기준 정렬
Arrays.sort(costs, (a, b) -> a[2] - b[2]);
public boolean union(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if (aRoot == bRoot)
return true;
parent[aRoot] = bRoot;
return false;
}
public int find(int n) {
if (n == parent[n])
return n;
return find(parent[n]);
}
Kruskal 전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public int solution(int n, int[][] costs) {
int ans = 0;
parent = new int[n];
for (int i = 0; i < n; i++)
parent[i] = i;
// 값 기준 정렬
Arrays.sort(costs, (a, b) -> a[2] - b[2]);
for (int i = 0; i < costs.length; i++) {
int a = costs[i][0];
int b = costs[i][1];
if (union(a, b))
continue;
ans += costs[i][2];
}
return ans;
}
public boolean union(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if (aRoot == bRoot)
return true;
parent[aRoot] = bRoot;
return false;
}
public int find(int n) {
if (n == parent[n])
return n;
return find(parent[n]);
}
표로 정리
| 프림 | 크루스칼 | |
|---|---|---|
| 핵심 | 노드 중심, 연결된 곳에서 가장 싼 간선 선택 | 간선 중심, 전체 간선 중 싼 것부터 선택 |
| 자료구조 | 인접 리스트 + PQ + visited[] | 간선 정렬 + Union-Find |
| 복잡도 | O(ElogV) | O(ElogE) |
| 추천 상황 | 간선이 많을 때 | 간선이 적을 때, 코드 간결함 |