[프로그래머스/lv3] 퍼즐조각 채우기
문제 정보
[프로그래머스/lv3] 퍼즐 조각 채우기
game_board의 빈 공간(0)과 table의 퍼즐 조각(1)을 비교하여 딱 맞게 채울 수 있는 조각의 칸 수를 구하는 구현 문제이다. 퍼즐 조각은 회전이 가능하지만 뒤집기는 불가능하며, 빈 공간보다 작거나 크면 사용할 수 없다.
입출력 예
game_boardtablereturn[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]][[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]]14
제약 조건
game_board와 table의 크기 : 1 ~ 50 game_board와 table은 0과 1로만 구성 퍼즐 조각은 90도 단위로 회전 가능, 뒤집기 불가 빈 공간에 딱 맞아야 하며 남거나 모자라면 사용 불가
풀이
DFS인척을 하는 구현 문제로써 꽤 빡센 구현 난이도를 가지고 있기에 천천히 task를 나누어 푸는게 유리한 문제이다.
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 좌표는 이미 정렬된 첫번째 요소를 사용한다. 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;
}
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를 채울 수 있을지 알 수 있다.