프로그래머스 - 퍼즐조각 맞추기

문제 설명

한 게임판과 퍼즐조각이 흩어져있는 판이 주어진다.

게임판에 비어있는 란에 흩어져있는 판에 있는 퍼즐을 끼워 넣어 빈 공란을 채우는 개수를 구하는 문제이다.

여기서의 핵심은 퍼즐조각이 위치한 판에서 도형을 추출하는 과정이 중요하다.

그리고 이 도형을 빈 공란에 맞춰 끼울 수 있는지 여부도 판단해야 한다.

나는 해당 도형을 BFS로 추출했다. 그리고 해당 정보를 가지고 객체를 생성했다.

객체는 해당 도형을 표현한 2차원 배열을 필드변수로 가지고 있다.

class Puzzle {
		int cnt; // 1의 개수
		int map[][];

		public Puzzle(int map[][], int cnt) {
			this.map = map;
			this.cnt = cnt;
		}
}

 

여러 도형들을 BFS로 추출하여 해당 칸에 타이트한 배열을 만들어 줬다.

마찬가지로 게임판에 있는 공란 또한 저런 형식으로 객체를 구성했다.

최종적으로 공란에 하나를 추출하여 하나의 퍼즐을 추출후 4번 도형 회전을 통해 맞는지 비교하는 형식으로 구현했다.

풀이

class Puzzle {
		int cnt; // 1의 개수
		int map[][];

		public Puzzle(int map[][], int cnt) {
			this.map = map;
			this.cnt = cnt;
		}

		public void rotate() {
			int n = map.length;
			int m = map[0].length;

			int newMap[][] = new int[m][n];

			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					newMap[i][j] = map[n - j-1][i];
				}
			}

			this.map = newMap;
		}

		public boolean isEqualSize(Puzzle otehr) {
			int n = this.map.length;
			int m = this.map[0].length;
			int on = otehr.map.length;
			int om = otehr.map[0].length;

			return n == on && m == om;
		}

		public boolean isTight(Puzzle empty) {
			for (int i = 0; i < this.map.length; i++) {
				for (int j = 0; j < this.map[i].length; j++) {
					if (empty.map[i][j] != this.map[i][j]) {
						return false;
					}
				}
			}

			return true;
		}
	}

	class Node {
		int y, x;

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

	}

	int[] dy = {-1, 1, 0, 0}, dx = {0, 0, -1, 1};
	int n, m;
	boolean v[][];

	public int solution(int[][] game_board, int[][] table) {
		int answer = 0;
		n = game_board.length;
		m = game_board[0].length;

		List<Puzzle> empties = new ArrayList<>();
		List<Puzzle> puzzles = new ArrayList<>();
		v = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (game_board[i][j] == 0 && !v[i][j]) {
					List<Node> emptyBlocks = getBlock(game_board, i, j, 0);

					List<Integer> yList = emptyBlocks.stream().map(node -> node.y).collect(Collectors.toList());
					List<Integer> xList = emptyBlocks.stream().map(node -> node.x).collect(Collectors.toList());

					int minY = yList.stream().min(Integer::compareTo).orElseGet(() -> 0);
					int maxY = yList.stream().max(Integer::compareTo).orElseGet(() -> 0);
					int minX = xList.stream().min(Integer::compareTo).orElseGet(() -> 0);
					int maxX = xList.stream().max(Integer::compareTo).orElseGet(() -> 0);
					int r = maxY - minY + 1;
					int c = maxX - minX + 1;
					int map[][] = new int[r][c];

					emptyBlocks.forEach(node -> map[node.y - minY][node.x - minX] = 2);

					empties.add(new Puzzle(map, emptyBlocks.size()));
				}
			}
		}

		v = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (table[i][j] == 1 && !v[i][j]) {
					List<Node> puzzleNodes = getBlock(table, i, j, 1);
					List<Integer> yList = puzzleNodes.stream().map(node -> node.y).collect(Collectors.toList());
					List<Integer> xList = puzzleNodes.stream().map(node -> node.x).collect(Collectors.toList());

					int minY = yList.stream().min(Integer::compareTo).orElseGet(() -> 0);
					int maxY = yList.stream().max(Integer::compareTo).orElseGet(() -> 0);
					int minX = xList.stream().min(Integer::compareTo).orElseGet(() -> 0);
					int maxX = xList.stream().max(Integer::compareTo).orElseGet(() -> 0);
					int r = maxY - minY + 1;
					int c = maxX - minX + 1;
					int map[][] = new int[r][c];

					puzzleNodes.forEach(node -> map[node.y - minY][node.x - minX] = 2);

					puzzles.add(new Puzzle(map, puzzleNodes.size()));
				}
			}
		}

		Set<Integer> usings = new HashSet<>();// 퍼즐 사용여부
		for (int i = 0; i < empties.size(); i++) {
			Puzzle emptyPuzzle = empties.get(i);

			for (int j = 0; j < puzzles.size(); j++) {
				if (usings.contains(j))
					continue;

				Puzzle puzzle = puzzles.get(j);

				if (emptyPuzzle.cnt != puzzle.cnt)
					continue;
				boolean isTight = false;
				for (int k = 0; k < 4; k++) {
					if (k != 0) {
						puzzle.rotate();
					}

					if (!emptyPuzzle.isEqualSize(puzzle))
						continue;

					if (emptyPuzzle.isTight(puzzle)) {
						isTight = true;
					}
				}

				// 되돌리기
				puzzle.rotate();

				if(isTight){
					usings.add(j);
					answer+=puzzle.cnt;
					break;
				}

			}
		}

		return answer;
	}

	List<Node> getBlock(int arr[][], int y, int x, int type) {
		LinkedList<Node> q = new LinkedList<>();
		q.offer(new Node(y, x));
		v[y][x] = true;

		List<Node> results = new ArrayList<>();
		results.add(new Node(y, x));

		while (!q.isEmpty()) {
			Node cur = q.poll();

			for (int i = 0; i < 4; i++) {
				int ny = dy[i] + cur.y;
				int nx = dx[i] + cur.x;

				if (isOutOfRange(ny, nx))
					continue;
				if (v[ny][nx])
					continue;
				if (arr[ny][nx] != type)
					continue;

				v[ny][nx] = true;
				q.offer(new Node(ny, nx));
				results.add(new Node(ny, nx));
			}
		}

		return results;
	}

	boolean isOutOfRange(int ny, int nx) {
		return ny < 0 || nx < 0 || ny >= n || nx >= m;
	}