체감 난이도 = 최상
https://school.programmers.co.kr/learn/courses/30/lessons/84021
문제분석 및 설계
각 칸을 노드로 보고 각 노드를 이어주는 선이 있다고 생각한 후 그 선을 엣지로 생각해서, 그래프 문제로 접근하였습니다.
게임보드 빈 칸에 딱 맞는 테이블 위의 퍼즐조각을 끼워넣을 때, 최대한 많은 칸을 채워야합니다.
보드의 빈 칸과 테이블의 퍼즐조각을 구하는 것은 dfs 혹은 bfs를 사용합니다.
dfs나 bfs로 완전탐색을 해도 그리드의 전체 크기는 50*50 이므로, O(2500+2500) = O(5000)이라 가능할 것으로 판단했습니다.
처음에는 테이블 위의 퍼즐조각을 dfs로 구한 후, 각 좌표를 list에 넣어두었습니다. 그런데 이렇게하니 회전시킨 퍼즐 정보는 어떻게 저장할지, 그리고 게임보드의 빈칸과 어떻게 비교할지가 어려웠습니다.
즉, 구현하는데에 어렵다고 느낀 로직은 아래와 같습니다.
1. 퍼즐조각을 어떻게 회전시키지?
2. 퍼즐조각과 게임 보드의 빈 칸이 빈틈없이 같은 모양인지 어떻게 판별하지?
코드가 복잡해지고 헷갈리는데, 해당 문제에 시간을 많이 써서 정답 코드를 보고 다시 공부하면서 풀었습니다.
정답 코드에서는 제가 위에서 말한 어려웠던 로직을 아래의 방법으로 해결했습니다.
-
퍼즐조각 90도 회전시키는 것을 위해, table 전체를 90도씩 회전시킨 것을 미리 3차원 배열에 만들어둡니다.
: 회전은 2중 for문으로 전체 칸을 돌면서 차례로 큐에 넣고, 회전시킨 위치에 차례대로 큐에서 값을 뺍니다. -
퍼즐조각을 탐색할 때, 시작위치의 좌표를 기준으로 저장해둡니다. 그리고 해당 퍼즐조각의 다른 좌표들은 기준좌표와 얼마나 차이나는지 계산합니다. game_board의 빈칸 시작 좌표를 기준좌표로 두고, 앞(퍼즐조각)에서 구한 차이만큼 이동해 칸을 검사했을 때, 그 칸이 빈 칸이면서 기준 빈칸과 동일한 집단으로 취급되는 빈칸이면 다음칸을 검사하고... 이 과정에서 유효하지 않은 칸이 발견되면 모양이 불일치한다고 판별합니다.
2-1. 이미 채운 퍼즐 모양의 칸은 그래프를 돌면서 또 검사하지 않도록 하기위해, game_board의 빈칸을 탐색하면서 각 칸의 묶음별로 번호를 매깁니다.
그리고 해당 번호를 인덱스로 가진 배열을 만들어서, 각 번호를 채웠는지 안채웠는지 체크합니다.
코드
import java.util.*;
class Solution {
private static int[] dy = {-1, 0, 1, 0};
private static int[] dx = {0, 1, 0, -1};
private static Queue<Pos> q = new LinkedList<>();
public int solution(int[][] game_board, int[][] table) {
var answer = 0;
var len = game_board.length;
var gameBoardBlockNum = BFS(len, game_board, 0);
var tableBlockNum = BFS(len, table, 1);
var gameBoardBlockUsed = new int[gameBoardBlockNum];
var gameBoardBlockCount = new int[gameBoardBlockNum];
var tableBlockUsed = new int[tableBlockNum];
var tableBlockCount = new int[tableBlockNum];
var tables = new int[4][len][len];
tables[0] = table;
for (int i = 0; i < 3; i++) {
tables[i + 1] = rotate(tables[i]);
}
for (int y = 0; y < len; y++) {
for (int x = 0; x < len; x++) {
gameBoardBlockCount[game_board[y][x]]++;
tableBlockCount[tables[0][y][x]]++;
}
}
for (int y = 0; y < len; y++) {
for (int x = 0; x < len; x++) {
if (game_board[y][x] < 2 || gameBoardBlockUsed[game_board[y][x]] == 1) {
continue;
}
var count = gameBoardBlockCount[game_board[y][x]];
if (fill(y, x, game_board, count, tables[0], tableBlockCount, tableBlockUsed)
|| fill(y, x, game_board, count, tables[1], tableBlockCount, tableBlockUsed)
|| fill(y, x, game_board, count, tables[2], tableBlockCount, tableBlockUsed)
|| fill(y, x, game_board, count, tables[3], tableBlockCount, tableBlockUsed)) {
gameBoardBlockUsed[game_board[y][x]] = 1;
System.out.println(count);
answer += count;
}
}
}
return answer;
}
private int BFS(int len, int[][] map, int ground) {
q.clear();
var blockNum = 2;
var visited = new int[len][len];
for (int y = 0; y < len; y++) {
for (int x = 0; x < len; x++) {
if (map[y][x] != ground) {
continue;
}
q.add(new Pos(y, x));
map[y][x] = blockNum;
visited[y][x] = 1;
while (!q.isEmpty()) {
var pos = q.poll();
for (int i = 0; i < 4; i++) {
var ny = pos.y + dy[i];
var nx = pos.x + dx[i];
if (ny < 0 || ny >= len || nx < 0 || nx >= len) {
continue;
}
if (map[ny][nx] != ground) {
continue;
}
if (visited[ny][nx] == 1) {
continue;
}
map[ny][nx] = blockNum;
visited[ny][nx] = 1;
q.add(new Pos(ny, nx));
}
}
blockNum++;
}
}
return blockNum;
}
private int[][] rotate(int[][] source) {
var q = new LinkedList<Integer>();
var target = new int[source.length][source.length];
for (int y = 0; y < source.length; y++) {
for (int x = 0; x < source.length; x++) {
q.add(source[y][x]);
}
}
for (int x = source.length - 1; x >= 0; x--) {
for (int y = 0; y < source.length; y++) {
target[y][x] = q.poll();
}
}
return target;
}
private boolean fill(int mapY, int mapX, int[][] map, int count, int[][] table, int[] tableBlockCounts, int[] tableBlockUsed) {
var visited = new int[table.length][table.length];
for (int y = 0; y < table.length; y++) {
for (int x = 0; x < table.length; x++) {
if (table[y][x] == 0) {
continue;
}
if (tableBlockUsed[table[y][x]] == 1) {
continue;
}
if (count != tableBlockCounts[table[y][x]]) {
continue;
}
q.clear();
q.add(new Pos(y, x));
visited[y][x] = 1;
var tableBlockCount = 1;
while (!q.isEmpty()) {
var pos = q.poll();
for (int i = 0; i < 4; i++) {
var ny = pos.y + dy[i];
var nx = pos.x + dx[i];
if (ny < 0 || ny >= table.length || nx < 0 || nx >= table.length) {
continue;
}
if (table[ny][nx] == 0 || table[ny][nx] != table[y][x]) {
continue;
}
if (visited[ny][nx] == 1) {
continue;
}
var nMapY = mapY + (ny - y);
var nMapX = mapX + (nx - x);
if (nMapY < 0 || nMapY >= table.length || nMapX < 0 || nMapX >= table.length
|| map[nMapY][nMapX] != map[mapY][mapX]) {
q.clear();
break;
}
visited[ny][nx] = 1;
q.add(new Pos(ny, nx));
tableBlockCount++;
}
}
if (tableBlockCount == count) {
tableBlockUsed[table[y][x]] = 1;
return true;
}
}
}
return false;
}
private static class Pos {
private int y;
private int x;
private Pos(int y, int x) {
this.y = y;
this.x = x;
}
}
}공부한 사항
- 3차원 배열을 머릿속에 넣어두고, 유용하게 사용하도록 신경써야겠다.
- 2차원 배열 회전 방법
: 큐에 특정 순서대로 모든 위치의 값을 넣고, 원하는 방향으로 회전시킨 후의 위치부터 순서대로 큐에서 값을 뺀다.
