[Programmers] 퍼즐 조각 채우기 (Level 3)
1. 문제 설명
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코테의 근본은 C++
하지만 최근 기업 코테에서 C++을 받아주질 않는 추세다.
이유가 뭔고 하니 C++로 해킹을 하는 사람들이 있다고......:(
그것도 있고 기업 코테의 목적이 알고리즘 그 자체보단, 언어의 이해도를 측정하는 구현 능력에 초점을 맞추면서 겸사겸사 제한하는 것 같다.
덕분에 코테도 자바로 하는데, 손에 안 익어서 죽을 맛이다.
2. 아이디어
생각 이상으로 시간을 너무 잡아먹었다.
3월 이후로 개발에 몰두한다고 코테 손 좀 놨더니 바로 폼 떨어져버림.
1️⃣ 블록 탐색
일단 처음 보자마자 떠올린 것, game_board에 들어가야 할 블록 타입과 table에서 제공해준 block을 확인하는 것.
다만 저장할 때, table에서 block의 위치를 저장하면 나중에 game_board의 블록과 비교할 때 상당히 번거로워질 것 같아서 (0, 0)을 기준으로 블록을 저장했다.
예를 들어, ②의 경우 [[0, 3], [0, 4], [1, 4], [2, 4], [2, 5]]지만, 저장할 때는 [[0, 0], [0, 1], [1, 1], [2, 0], [2, 1]]이 된다.
문제는 이 때는 고려하질 못 했었는데 ①과 같은 케이스 때문에 상당히 애먹었다.
좌측 상단부터 탐색을 하므로, 저장될 때 [[0, 0], [1, 0], [2, 0], [1, -1]]로 저장이 된다.
나중에 회전시킬 때 좌표 정렬 기준을 생각 안 하면 피를 본다 ㅎㅎ
class Solution {
private static final int[][] dydx = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private static int N;
private List<List<Node>> empties = new ArrayList<>();
private List<List<Node>> blocks = new ArrayList<>();
public int solution(int[][] game_board, int[][] table) {
N = table.length;
boolean[][] boardVisited = new boolean[N][N], tableVisited = new boolean[N][N];
for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) {
if (game_board[i][j] == 0 && !boardVisited[i][j]) findBlock(i, j, 0, boardVisited, game_board);
if (table[i][j] == 1 && !tableVisited[i][j]) findBlock(i, j, 1, tableVisited, table);
}
...
}
...
}private static class Node implements Comparable<Node> {
private int row;
private int col;
Node(int row, int col) {
this.row = row;
this.col = col;
}
int row() {return this.row;}
int col() {return this.col;}
@Override
public int compareTo(Node node) {
int tmp = Integer.compare(this.row, node.row());
return (tmp != 0) ? tmp : Integer.compare(this.col, node.col());
}
@Override
public String toString() {
return "(row = " + row + ", col = " + col + ")";
}
}c++처럼 struct나 pair를 쓸 수 있으면 차암~~~~~ 좋겠지만, 안 되니까 좌표 저장용 데이터 타입 클래스를 하나 정의해주었다.
객체 지향 설계 원칙에 예민한 타입이라 습관 처럼 전부 private를 걸긴 했는데, 코테용 코드라서 굳이 이렇게까지 할 이유가...😅
Comparable을 구현해준 이유는 나중에 회전시키면 좌표값이 죄다 뒤틀려버리기 때문.
이 때, 반드시 row를 우선적으로 비교해주어야 한다.
진짜 얼탱이 없는 부분인데, 위에서 언급했듯이 회전시킬 때 ①과 같은 케이스가 문제가 된다.
나머진 아래에서 회전 코드 다룰 때 설명
(toString을 재정의한 이유는..내가 디버깅한다고...)
private void findBlock(int y, int x, int target, boolean[][] visited, int[][] board) {
visited[y][x] = true;
Queue<Node> q = new LinkedList<>();
q.offer(new Node(y, x));
List<Node> tmp = new ArrayList<>();
tmp.add(new Node(0, 0));
while (!q.isEmpty()) {
Node cur = q.poll();
for (int i=0; i<4; ++i) {
int ny = cur.row() + dydx[i][0];
int nx = cur.col() + dydx[i][1];
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
if (visited[ny][nx] || board[ny][nx] != target) continue;
visited[ny][nx] = true;
q.offer(new Node(ny, nx));
tmp.add(new Node(ny - y, nx - x));
}
}
if (target == 1) {
blocks.add(tmp);
} else {
Collections.sort(tmp);
empties.add(tmp);
}
}찾는 거야 그냥 BFS 로직이라 간단하게 구현 가능.
blocs는 어차피 나중에 회전시킬 때마다 정렬해줘야 해서, game_board의 블록 리스트들만 정렬해주었다.
2️⃣ 대조할 block 고르기
private int findAnswer() {
int res = 0;
boolean[] visited = new boolean[blocks.size()];
for (int i=0; i<empties.size(); ++i) for (int j=0; j<blocks.size(); ++j) {
if (visited[j] || empties.get(i).size() != blocks.get(j).size()) continue;
if (isValid(empties.get(i), blocks.get(j))) {
visited[j] = true;
res += blocks.get(j).size();
break;
}
}
return res;
}block을 대조할 때는 그냥 무식하게 하나하나 비교했다.
다만, table에서 이미 사용한 블럭을 재사용하면 안 되니까 visited를 blocks 사이즈만큼 만들어주고 사용 여부 체크를 해주어야 한다.
3️⃣ 회전시키면서 block 대조해보기
private boolean isValid(List<Node> emptyNodes, List<Node> blockNodes) {
for (int i=0; i<4; ++i) {
Collections.sort(blockNodes);
int curY = blockNodes.get(0).row(), curX = blockNodes.get(0).col();
for (Node node : blockNodes) {
node.minusRowAndCol(curY, curX);
}
if (isSameNodes(emptyNodes, blockNodes)) {
return true;
}
rotate(blockNodes);
}
return false;
}각도가 0, 90, 180, 270마다 비교해봐야 하니, 반복문은 4번 돌려주면 된다.
우선 회전시킬 때마다 좌표 재정렬 시켜줘야 하기도 하고, 아까 bfs 돌릴 때도 정렬해준 적 없으므로 가장 처음에 해줘야 한다.
그 다음이 중요한데, 왜 row와 col 업데이트를 하냐?
회전이 안 된 상태면, 어차피 game_board나 table이나 같은 탐색 순서로 읽었으므로, 같은 앵글의 같은 도형이면 일치할 것이다.
하지만 그게 아니라면 회전을 시켜줘야 하는데, 나는 그냥 속편하게 원점 기준 좌표 90도 회전 공식을 써버렸다.
그랬더니 좌표를 정렬시켜주면 (0, 0)이 아니라 c번처럼 (-1, -1)이 나오는 경우가 생기는데, 이걸 다시 원점으로 밀어주려면 가장 작은 값을 갖는 좌표값을 기준으로 모든 좌표를 이동시켜주면 된다. (즉, (-1, -1)이 (0, 0)으로 갈 수 있도록 조정하면 된다.)
다만 여기서 주의해야 할 게 있는데, 위에서 계속 이야기했던 정렬 순서 때문이다.
위와 같은 케이스가 나왔을 때, (-1, -1)처럼 이동의 지배적인 기준이 없는 경우, 두 가지 경우로 나뉜다.
더 작은 row를 갖는 좌표를 (0, 0)으로 만들 것이냐, 더 작은 col을 갖는 좌표를 (0, 0)으로 만들 것이냐.
정답은 반드시 row를 기준으로 맞춰야만 한다.
그렇지 않으면 모양은 같은데 좌표가 달라서 비교가 틀린다.
어차피 같은 정렬을 갖는데, 그게 왜 문제가 되는지 의아할 수 있지만, game_board의 탐색 순서를 생각해보자.
예시와 동일한 모양이 존재할 때 "언제나 더 작은 row를 갖는 좌표가 (0, 0)"이 되기 때문이다.
따라서 회전시키고 재정렬할 때도 row를 기준으로 정렬해주어야 한다.
private boolean isSameNodes(List<Node> emptyNodes, List<Node> blockNodes) {
for (int idx=0; idx<emptyNodes.size(); ++idx) {
if (emptyNodes.get(idx).row() != blockNodes.get(idx).row() || emptyNodes.get(idx).col() != blockNodes.get(idx).col()) {
return false;
}
}
return true;
}
private void rotate(List<Node> nodes) {
for (Node node : nodes) {
node.rotate();
}
}비교야 간단하고, rotate도 Node 내부에서 처리하도록 만들었다.
4️⃣ Node 내부 메서드 추가
private static class Node implements Comparable<Node> {
...
void minusRowAndCol(int row, int col) {
this.row -= row;
this.col -= col;
}
void rotate() {
int tmp = this.row;
this.row = col;
col = -tmp;
}
...
}짠, 이렇게 하면 끝난다.
다른 사람들은 어떻게 했나 구경해봤는데, 블록 좌표만 저장하는 게 아니라 가장 작은 사이즈에 맞춰서 맵을 새롭게 그려주고 있었다.
아마 회전이 간단해지기 때문이라 생각하는데, 나도 이걸 떠올리지 못한 건 아니다.
그저 블록 갯수를 매번 다시 카운트하거나, 따로 저장해두어야 하는데 이게 귀찮아서 블록 좌표만 저장했다.
근데 괜히 한 듯 ㅋ
3. 코드
import java.util.*;
class Solution {
private static final int[][] dydx = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private static int N;
private List<List<Node>> empties = new ArrayList<>();
private List<List<Node>> blocks = new ArrayList<>();
public int solution(int[][] game_board, int[][] table) {
N = table.length;
boolean[][] boardVisited = new boolean[N][N], tableVisited = new boolean[N][N];
for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) {
if (game_board[i][j] == 0 && !boardVisited[i][j]) findBlock(i, j, 0, boardVisited, game_board);
if (table[i][j] == 1 && !tableVisited[i][j]) findBlock(i, j, 1, tableVisited, table);
}
return findAnswer();
}
private void findBlock(int y, int x, int target, boolean[][] visited, int[][] board) {
visited[y][x] = true;
Queue<Node> q = new LinkedList<>();
q.offer(new Node(y, x));
List<Node> tmp = new ArrayList<>();
tmp.add(new Node(0, 0));
while (!q.isEmpty()) {
Node cur = q.poll();
for (int i=0; i<4; ++i) {
int ny = cur.row() + dydx[i][0];
int nx = cur.col() + dydx[i][1];
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
if (visited[ny][nx] || board[ny][nx] != target) continue;
visited[ny][nx] = true;
q.offer(new Node(ny, nx));
tmp.add(new Node(ny - y, nx - x));
}
}
if (target == 1) {
blocks.add(tmp);
} else {
Collections.sort(tmp);
empties.add(tmp);
}
}
private int findAnswer() {
int res = 0;
boolean[] visited = new boolean[blocks.size()];
for (int i=0; i<empties.size(); ++i) for (int j=0; j<blocks.size(); ++j) {
if (visited[j] || empties.get(i).size() != blocks.get(j).size()) continue;
// System.out.println("================");
// System.out.println(empties.get(i));
// System.out.println(blocks.get(j));
if (isValid(empties.get(i), blocks.get(j))) {
visited[j] = true;
// System.out.println("성공!!!!");
res += blocks.get(j).size();
break;
}
}
return res;
}
private boolean isValid(List<Node> emptyNodes, List<Node> blockNodes) {
for (int i=0; i<4; ++i) {
Collections.sort(blockNodes);
int curY = blockNodes.get(0).row(), curX = blockNodes.get(0).col();
// System.out.println("**************");
// System.out.println("pre -> " + blockNodes);
for (Node node : blockNodes) {
node.minusRowAndCol(curY, curX);
}
// System.out.println("now -> " + blockNodes);
// System.out.println("**************");
if (isSameNodes(emptyNodes, blockNodes)) {
return true;
}
rotate(blockNodes);
}
return false;
}
private boolean isSameNodes(List<Node> emptyNodes, List<Node> blockNodes) {
for (int idx=0; idx<emptyNodes.size(); ++idx) {
if (emptyNodes.get(idx).row() != blockNodes.get(idx).row() || emptyNodes.get(idx).col() != blockNodes.get(idx).col()) {
return false;
}
}
return true;
}
private void rotate(List<Node> nodes) {
for (Node node : nodes) {
node.rotate();
}
}
private static class Node implements Comparable<Node> {
private int row;
private int col;
Node(int row, int col) {
this.row = row;
this.col = col;
}
int row() {return this.row;}
int col() {return this.col;}
void minusRowAndCol(int row, int col) {
this.row -= row;
this.col -= col;
}
void rotate() {
int tmp = this.row;
this.row = col;
col = -tmp;
}
@Override
public int compareTo(Node node) {
int tmp = Integer.compare(this.row, node.row());
return (tmp != 0) ? tmp : Integer.compare(this.col, node.col());
}
@Override
public String toString() {
return "(row = " + row + ", col = " + col + ")";
}
}
}