문제 링크 :
https://school.programmers.co.kr/learn/courses/30/lessons/84021#
코드를 알아보기 전에 먼저 문제와 알고리즘을 이해하여 스스로의 힘으로 코드를 짜보는 시간을 갖길 바랍니다.
문제 이해하기
게임 보드에 있는 빈 칸에 테이블에 있는 퍼즐 조각 중 일치하는 조각을 채우는 문제입니다.
우리는 위 예제를 보고 쉽게 어떤 조각이 어떤 빈 칸으로 들어가야 할지 알아차릴 수 있지만, 컴퓨터가 이를 한 눈에 알 순 없겠죠.
먼저 테이블 한 칸, 한 칸을 탐색한 후 어떤 모양의 퍼즐이 있는지 파악한 후, 게임 보드도 마찬가지로 빈 칸을 탐색해 그에 맞는 퍼즐이 있는지 찾아야 합니다.
이때, 퍼즐 조각과 빈 칸의 모양이 일치하지 않더라도 퍼즐 조각을 회전할 시에 일치한다면 빈 칸에 맞는 퍼즐 조각이라 할 수 있습니다.
- 조각은 한 번에 하나씩 채워 넣습니다.
- 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
위와 같은 규칙에 따라 하나의 빈 칸에 여러 퍼즐 조각이 들어갈 수는 없습니다.
즉, 빈 칸에 완전히 일치하지 않는 조각을 빈 칸에 넣으면 안된다는 거죠.
결론
결과적으로 이 문제는 아래와 같이 세 개의 문제들로 쪼개어지게 됩니다.
- 게임 보드와 테이블을 탐색해 빈 칸과 퍼즐 조각을 찾는 문제
- 퍼즐 조각을 회전 시키는 문제
- 퍼즐 조각과 빈칸이 일치하는지 판별하는 문제
알고리즘 이해하기
행렬 탐색 문제
해당 문제는 게임 보드 행렬과 테이블 행렬을 처음부터 끝까지 탐색해야 하는 완전 탐색의 문제이므로 DFS나 BFS 알고리즘을 사용할 수 있습니다.
둘 중 어떤 알고리즘을 사용해도 좋으나, 저는 제 편의에 맞게 DFS로 알고리즘을 짜보았습니다.
- 행렬의 현재 위치를 탐색한 것으로 표시한다.
- 행렬의 현재 위치를 리스트에 기록한다.
- 현재 위치에서 주위(상, 하, 좌, 우)에 이어지는 빈 칸 또는 퍼즐 조각이 있고 해당 위치를 탐색한 적이 없다면 해당 위치로 이동한다.
- 주위에 더 이상 탐색할 빈 칸 또는 퍼즐 조각이 없을 때까지 1-3 과정을 반복한다.
위 과정에서 새로운 행렬을 만들어 빈 칸 또는 퍼즐 조각 모양 대로 0또는 1을 기록하여 모양을 파악할 수도 있지만, 회전과 비교 시 복잡해질 수 있기에 리스트에 모양의 위치만 기록해두는 방법을 택했습니다.
아래의 규칙에 따라 각 칸을 x와 y로 위치를 잡아둡니다.
빈 칸 및 퍼즐 조각의 가장 왼쪽이고 맨 위인 블록(이하 '루트 블록')의 위치를 x와 y가 0인 기준점(00)으로 잡고, 오른쪽일 수록 x+1, 왼쪽일 수록 x-1, 위일 수록 y-1, 아래일 수록 y+1하여 리스트에 기록합니다.
이 규칙에 따르면 테이블에 있는 퍼즐 조각들은 아래와 같이 리스트로 저장됩니다.
- 00 01
- 00 10 11 12 22
- 00 10 02 -11
- 00 10 11
- 00 10
퍼즐 조각 회전 문제
위와 같이 퍼즐 조각들이 기록되어 있다는 걸 전제로 알고리즘을 고안했습니다.
- y를 음수로 바꾸고 x와 y를 반전한다. (시계 방향으로 90도 회전)
- 루트 블록의 x, y의 값을 모든 블록의 x, y에 빼준다.
- 루트 블록의 index가 0이 될 수 있도록 블록을 다시 정렬한다.
빈 칸과 조각 비교 문제
- 게임 보드에서 빈 칸을 찾는다.
- 빈 칸과 일치하는 퍼즐 조각을 찾고 일치하지 않는다면 퍼즐 조각을 회전 시켜 다시 일치 여부를 확인한다.
- 다음 빈 칸이 없을 때까지 1-2의 과정을 반복한다.
tip
- 회전 시 쉽게 루트 블록을 찾기 위해 정렬을 사용해보세요.
- 비교 시 같은 모양이더라도 다르게 정렬되어 있을 수 있습니다.
- 손 쉬운 비교를 위해 각 블록의 x와 y를 문자열로 묶어 기록해보세요.
- 비교 시 join() 메서드를 이용해보세요.
- 블록의 갯수가 같은 퍼즐 조각끼리만 비교해보세요.
문제 해결 코드(java)
문제가 3개로 나눠진만큼 코드가 조금 깁니다.
이해를 위해 주석도 꼼꼼히 달아봤으니 천천히 읽어보세요.
import java.util.ArrayList;
import java.util.Collections;
class Solution {
boolean[][] visited;
public int solution(int[][] game_board, int[][] table) {
int answer = 0;
// 퍼즐 조각을 담을 리스트.
ArrayList<ArrayList<String>> pieces = new ArrayList<>();
visited = new boolean[table.length][table[0].length];
// 테이블에서 퍼즐 조각을 탐색해 리스트에 담음.
for(int i = 0; i < table.length; i++){
for(int j = 0; j < table[0].length; j++){
if(table[i][j] == 1 && !visited[i][j]){
pieces.add(new ArrayList<>());
ArrayList<String> tmp = pieces.get(pieces.size()-1);
dfs(tmp, table, i, j, 0, 0, 1);
listSort(tmp);
}
}
}
// visited 초기화.
visited = new boolean[table.length][table[0].length];
for(int i = 0; i < game_board.length; i++){
for(int j = 0; j < game_board[0].length; j++){
// 게임보드에서 빈 칸 찾기.
if(game_board[i][j] == 0 && !visited[i][j]){
ArrayList<String> list = new ArrayList<>();
dfs(list, game_board, i, j, 0, 0, 0);
listSort(list);
// 조각들을 빈 칸에 맞춰 보는 과정.
for(int k = 0; k < pieces.size(); k++){
ArrayList<String> piece = pieces.get(k);
boolean isDone = false;
if(piece.size() != list.size()) continue;
for(int l = 0; l < 4; l++){
//System.out.println("빈칸 : " + list);
//System.out.println("퍼즐 조각 : " + piece);
//System.out.println();
// 빈 칸과 조각이 일치.
if(String.join(" ", piece).equals(String.join(" ", list))){
answer += list.size();
pieces.remove(k--);
// 일치한 조각은 리스트에서 삭제.
isDone = true;
break;
}
else{
//일치하지 않으면 조각을 회전.
rotate(piece);
//System.out.println("90도 회전");
}
}
if(isDone) break;
// 일치한 조각이 있다면 더 이상 새로운 조각을 맞춰보지 않음.
}
}
}
}
return answer;
}
// 빈 칸 및 퍼즐 조각 찾기.
void dfs(ArrayList<String> list, int[][] array, int i, int j, int x, int y, int n){
// 첫 블록(루트블록) 처리.
if(x == 0 && y == 0){
visited[i][j] = true;
list.add(x + " " + y);
}
// 상
if(i != array.length-1 && array[i+1][j] == n && !visited[i+1][j]){
visited[i+1][j] = true;
list.add(x + " " + (y+1));
dfs(list, array, i+1, j, x, y+1, n);
}
// 하
if(i != 0 && array[i-1][j] == n && !visited[i-1][j]){
visited[i-1][j] = true;
list.add(x + " " + (y-1));
dfs(list, array, i-1, j, x, y-1, n);
}
// 좌
if(j != 0 && array[i][j-1] == n && !visited[i][j-1]){
visited[i][j-1] = true;
list.add((x-1) + " " + y);
dfs(list, array, i, j-1, x-1, y, n);
}
// 우
if(j != array[0].length-1 && array[i][j+1] == n && !visited[i][j+1]){
visited[i][j+1] = true;
list.add((x+1) + " " + y);
dfs(list, array, i, j+1, x+1, y, n);
}
}
//퍼즐 조각 회전 (시계방향 90도)
void rotate(ArrayList<String> list){
for(int i = 0; i < list.size(); i++){
String str = list.get(i);
String[] splited = str.split(" ");
int x = Integer.parseInt(splited[0]);
int y = Integer.parseInt(splited[1]);
list.set(i, (y*-1) + " " + x);
// y를 음수로 변환 후, x와 y 반전.
}
listSort(list);
int x0 = 0;
int y0 = 0;
for(int i = 0; i < list.size(); i++){
String str = list.get(i);
String[] split = str.split(" ");
int x = Integer.parseInt(split[0]);
int y = Integer.parseInt(split[1]);
if(i == 0){ // 루트블록의 x와 y를 기록.
x0 = x;
y0 = y;
}
list.set(i, (x - x0) + " " + (y - y0));
// 모든 블록의 x와 y에 루트블록의 x, y를 뺌.
}
listSort(list);
}
// 루트블록이 list의 가장 앞에 오도록 하는 정렬.
void listSort(ArrayList<String> list){
list.sort((s1, s2) -> {
String[] split1 = s1.split(" ");
String[] split2 = s2.split(" ");
if (Integer.parseInt(split1[1]) == Integer.parseInt(split2[1]))
return Integer.parseInt(split1[0]) - Integer.parseInt(split2[0]);
return Integer.parseInt(split1[1]) - Integer.parseInt(split2[1]);
});
}
}출력 내용
예제로 주어진 값으로 출력했을 때 아래의 결과를 볼 수 있습니다.
결과적으로 어떤 과정으로 퍼즐을 맞추게 되는지 보기 위해 구현한 것이므로 반드시 구현할 필요는 없습니다.
빈칸 : [0 0, 1 0, 1 1, 1 2, 2 2]
퍼즐 조각 : [0 0, 1 0, 1 1, 1 2, 2 2]
빈칸 : [0 0, 0 1]
퍼즐 조각 : [0 0, 0 1]
빈칸 : [0 0, 1 0, 0 1]
퍼즐 조각 : [0 0, 1 0, 1 1]
90도 회전
빈칸 : [0 0, 1 0, 0 1]
퍼즐 조각 : [0 0, -1 1, 0 1]
90도 회전
빈칸 : [0 0, 1 0, 0 1]
퍼즐 조각 : [0 0, 0 1, 1 1]
90도 회전
빈칸 : [0 0, 1 0, 0 1]
퍼즐 조각 : [0 0, 1 0, 0 1]
빈칸 : [0 0, -1 1, 0 1, 1 1]
퍼즐 조각 : [0 0, -1 1, 0 1, 0 2]
90도 회전
빈칸 : [0 0, -1 1, 0 1, 1 1]
퍼즐 조각 : [0 0, -1 1, 0 1, 1 1]