EunSung.log

퍼즐 조각 채우기

5 min read

문제 정보

풀이

접근 자체는 간단하다. BFS/DFS를 쓰긴 하는데, 그보다는 ‘구현’에 중점을 둔 문제다.

게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안됩니다. 라는 조건을 잘 생각해보면 퍼즐 조각을 딱 맞는 공간에 끼워 넣어야 한다는 것임을 알 수 있다. 즉 다시 말해서, 빈 칸과 퍼즐 조각의 모양이 같은지 확인하면 된다.

코드는 크게 이하 4개로 구성된다.

  1. 조각 추출
    • BFS/DFS로 연결된 1 (또는 0)을 하나로 묶음
  2. 좌표 정규화
    • 비교가 용이하도록 좌표를 정규화
    • (x, y) → (x - minX, y - minY)로 구현
  3. 퍼즐 조각 회전
    • 조각을 90° 회전
    • (x, y) → (y, -x)로 구현
    • 회전한 후 다시 정규화해야 함
  4. 퍼즐 조각 매칭
    • 빈 칸에 대해 퍼즐 조각을 회전시키면서 모양이 같은지 확인

코드

import java.util.*;
 
class Point {
	final int x, y;
	
	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	@vOverride
	public boolean equals(Object o) {
		if (this == o) return true;
		if (!(o instanceof Point)) return false;
		Point p = (Point) o;
		return x == p.x && y == p.y;
	}
	
	@Override
	public int hashCode() {
		return Objects.hash(x, y);
	}
}
 
class Solution {
	public int solution(int[][] game_board, int[][] table) {
		int n = game_board.length;
		
		List<Set<Point>> blanks = extract(game_board, 0);
		List<Set<Point>> pieces = extract(table, 1);
		
		int answer = 0;
		boolean[] isUsed = new boolean[pieces.size()];
		
		for (Set<Point> blank : blanks) {
			for (int i = 0; i < pieces.size(); i++) {
				if (isUsed[i]) continue;
				
				Set<Point> rotated = new HashSet<>(pieces.get(i));
				boolean isMatched = false;
				for (int j = 0; j < 4; j++) {
					if (blank.equals(rotated)) {
						answer += blank.size();
						isUsed[i] = true;
						isMatched[i] = true;
						break;
					}
					rotated = rotate(rotated);
				}
				
				if (isMatched) break;
			}
		}
		
		return answer;
	}
	
	private List<Set<Point>> extract(int[][] board, int target) {
		int n = board.length;
		boolean[][] isVisited = new boolean[n][n];
		List<Set<Point>> blocks = new ArrayList<>();
		int[][] DIR = { {0, 1}, {1, 0}, {-1, 0}, {0, -1}};
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i][j] == target && !isVisited[i][j]) {
					Queue<int[]> q = new LinkedList<>();
					
					q.add(new int[]{i, j});
					isVisited[i][j] = true;
					List<Point> temp = new ArrayList<>();
					
					while (!q.isEmpty()) {
						int[] cur = q.poll();
						temp.add(new Point(cur[0], cur[1]));
						
						for (int[] dir : DIR) {
							int dx = cur[0] + dir[0];
							int dy = cur[1] + dir[1];
							
							if (dx < 0 || dy < 0 || dx >= n || dy >= n) continue;
							if (isVisited[dx][dy]) continue;
							if (board[dx][dy] != target) continue;
							
							isVisited[dx][dy] = true;
							q.add(new int[]{dx, dy});
						}
					}
					
					blocks.add(normalize(temp));
				}
			}
		}
		
		return blocks;
	}
	
	private Set<Point> normalize(List<Point> blocks) {
		int minX = Integer.MAX_VALUE;
		int minY = Integer.MAX_VALUE;
		
		for (Point p : blocks) {
			minX = Math.min(minX, p.x);
			minY = Math.min(minY, p.y);
		}
		
		Set<Point> normalized = new HashSet<>();
		for (Point p : block)
			normalized.add(new Point(p.x - minX, p.y - minY));
			
		return normalized;
	}
	
	private Set<Point> rotate(Set<Point> block) {
		List<Point> rotated = new ArrayList<>();
		
		for (Point p : block)
			rotated.add(new Point(p.y, -p.x));
			
		return normaliz(rotated);
	}
}

여담

처음에는 조각 하나의 칸의 좌표를 List<int[]>로 저장했다.

그 때문에 같은 모양인지 비교할 때 좌표를 하나하나 비교해야 했다. 그런데 코드를 작성하는 중에 HashSet을 사용하면 HashSet.equals()를 사용하면 더 간단하게 작성할 수 있다는 것을 알게 되었다.

그래서 x, y 좌표를 하나의 문자열로 만들어 HashSet에 넣고 HashSet.equals()로 비교했다가 좌표를 별도의 클래스로 관리하도록 수정한 것이 위의 코드이다.

전반적으론 현재 코드가 더 빠른데, 몇몇 테스트 케이스에선 눈에 띌 정도로 느렸다.

백링크