728x90
(원래 전부터 풀던건데 테케 3개를 통과 못해서 안되고있었다....바보같이 한줄을 빼먹어서 그랬다. 그래서 다른 공부도 못하고 진도가 느려짐.......)
문제 설명
1. board와 table이 각각 배열로 주어진다.
2. 0은 빈칸, 1은 블록으로 채워진 부분이다.
3. board의 빈 부분을 table의 블록으로 채워주면 된다.
4. 블록은 회전할 수 있고, 뒤집을수는 없다. 빈칸은 하나의 블록으로 딱 맞게 채워야만 한다.
이를 채우면
이렇게 되는 것이고, 답은 '14'를 return하게 된다.
풀이 과정
진짜 힘들게 구했다...풀이 알고리즘 자체는 생각하기 쉬운데, 이를 구현하는 것이 힘들다.
1. 먼저 각각 game_board의 경우는 빈칸(0) , table의 경우는 블록(1) 에 해당하는 것들의 좌표를 구해 준다.
- 이 블록들을 DFS 돌린 후에 값들을 (0, 0)기준으로 배치시켜 넣는 로직이다. (0, 0)기준으로 배치시키는 이유는 후술.
블록들마다 맞춰서 수행해준다.
check = new boolean[배열X길이][배열Y길이];
for(int i=0; i<배열X길이; i++){
for(int j=0; j<배열Y길이; j++){
if(!check[i][j] && 구하려는 배열[i][j]==[game_board는1 / table은 0]){
boardCnt = 0; // 현재 기준부터 시작하여 DFS를 통해 가져올 범위의 크기이다.
minX = 배열X길이; // X쪽 최소길이
maxX = 0; // X쪽 최대길이
minY = 배열Y길이;
maxY = 0;
boardFigureMaker(game_board, i, j); // 배열에서 값들을 좌표형식으로 뽑아내려 한다. DFS를 쓸 예정
for(int cnt=0; cnt<boardCnt; cnt++){
int ans[] = new int[2]; // 가져온 것은 좌표평면이니까 x,y축 2개로 받기
ans = boardFigure.poll(); // queue로 가져온 좌표평면 이중배열을 출력
ans[0] -= minX; // ans[0]이 좌표의 x축이다. 그런데 회전을 해야 하므로 가장 먼저 나오는 x를 0에 위치시키기 위해 minX만큼 뺴줌
ans[1] -= minY; // Y도 마찬가지...이렇게 하면 가져온 좌표평면이 (0, 0)을 기주으로 놓여진다.
AfterboardFigure.offer(ans); // 그렇게 좌표평면으로 만든 내용을 다른 Queue에 넣어줌.
}
AfterboardFigure.offer(new int[]{-1, -1}); // 여러 블록을 가져올 것이므로, 절대 안나올 -1, -1을 기준으로 도형을 판단한다.
}
}
}- DFS로직이다. 이를 통해 처음에 2차원 배열로 나타난 각각 모습을 좌표평면으로 바꾸어 줄 수 있다.
사실 DFS는 다른 포스트에서 지겹게 적어서 따로 설명은 스킵한다~
public static void tableFigureMaker(int[][] table, int x, int y){
if(x<0 || x>=xArea || y<0 || y>=yArea) return;
if(check[x][y] || table[x][y]==0 또는 1) return;
tableCnt++; // 블록의 크기를 잰다.
check[x][y] = true;
maxX = Math.max(maxX, x);
minX = Math.min(minX, x);
maxY = Math.max(maxY, y);
minY = Math.min(minY, y); // 그 블록의 최대XY, 최소XY모두 구해줌. <- 사실 최소만 구해도 무방하다.
tableFigure.offer(new int[]{x, y}); // 좌표평면을 Queue에 넣는다.
for(int i=0; i<4; i++){
tableFigureMaker(table, x+Xmove[i], y+Ymove[i]);
}
}
2. 이제 각각의 Queue에 좌표평면으로 이루어진 값들이 담겼다. 이는 (-1, -1)으로 구분될 것이다.
그러면 비교를 위한 process를 시작해야 한다.
- board쪽에 table이 들어가야 한다. 즉 table을 기준으로 두고 board를 싹 확인하여 없으면 걍 버려버리면 된다.
그래서 나는 table에서 만든 블록을 기준으로 돌릴거다.
while(!AftertableFigure.isEmpty()){
int nowTable[] = new int[2]; // X Y축 좌표를 구할 nowTable
nowTable = AftertableFigure.poll(); // 아까 만들어준 블록을 가져와서 꺼내준다.
if(nowTable[0]==-1 && nowTable[1]==-1){ // 여기까지 가져오면 한 도형이 끝나는 것이다. 도형이 만들어졌으니 확인 시작.
int Xleng = maxX-minX+1; // X축 길이 Xleng
int Yleng = maxY-minY+1; // 이건 Y축
int temp[][] = new int[Xleng][Yleng]; // 처음에 만들어진 블록을 도형 크기에 맞추어서 temp에 저장시킨다.
for(int i=0; i<Xleng; i++){
for(int j=0; j<Yleng; j++){
temp[i][j] = nowFigure[i][j]; // 이렇게 만들면 도형의 길이, 높이에 맞추어 딱 짤림.
}
}
for(int num=0; num<4; num++){ // 이쪽이 회전 logic이다.
temp = rotate(temp); / rotate함수를 돌면 90도 돌아감..
int compare = coordinater(temp, temp.length, temp[0].length); // coordinater는 좌표 확인해서 체크하고, 맞으면 도형 크기를 return해주는 함수이다.
if(compare!=0) answer += compare; // coordinater에서 값이 왔다는건 답이 있다는거
if(compare!=0) break; // 이게 맞는 블록이므로 더 돌릴것도 없다.
}
nowFigure = new int[11][11]; // 초기화~
maxX = 0;
maxY = 0;
minX = 11;
minY = 11;
continue; // 기껏 초기화 해놓고 밑에서 최대 최소 구하면 현재 블록 기준으로됨. 그래서 continue로 무시
}
nowFigure[nowTable[0]][nowTable[1]]++; // 그 위치에 맞는 좌표평면 그리기
maxX = Math.max(maxX, nowTable[0]); // 좌표도 나는 (0, 0)기준으로 만들거다. 그래서 최대최소 받아옴.
minX = Math.min(minX, nowTable[0]);
maxY = Math.max(maxY, nowTable[1]);
minY = Math.min(minX, nowTable[1]);
}- 회전 로직 rotate
public static int[][] rotate(int[][] m) {
int N = m.length;
int M = m[0].length;
// 돌린 크기만큼으로 생성해준다.
int[][] copyMap = new int[M][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copyMap[j][N - 1 - i] = m[i][j];
}
}
// 새로 돌린 배열로 반환해준다.
return copyMap;
}
3. 이제 돌리는것도 됐고 체크만 하면 된다.
- 체크용 coordinater
public static int coordinater(int[][] num, int Xin, int Yin){ // table블록, 크 XY축
int nowFigureSize = 0; // 딱맞는 도형의 크기를 return할 값
int nowFigure[][] = new int[11][11]; // board쪽에서 만들 좌표..나중에 작아짐.
int maxX = 0;
int maxY = 0;
int minX = 11;
int minY = 11; // 테이블 크기 작게 하기 위한 것들.
boolean notDiff = true; // 둘이 다른거면 나가야한다.
Queue<int[]> tempSave = new LinkedList<>(); // board쪽은 table의 블록과 달라도 다른 table과 비교해야 하므로 버리면 안됨. 그래서 저장해야한다.
int sizeBoard = AfterboardFigure.size(); // 하나씩 빼면서 검사하니까 미리 전체 크기 가져옴
for(int cnt=0; cnt<sizeBoard; cnt++){ // 좌표 만드는건 위의 로직과 비슷하므로 위를 참고할것.
int nowTable[] = new int[2];
nowTable = AfterboardFigure.poll();
tempSave.offer(nowTable);
if(nowTable[0]==-1 && nowTable[1]==-1){
int Xleng = maxX-minX+1;
int Yleng = maxY-minY+1;
if(Xleng!=Xin || Yleng!=Yin){ // 만들어진 값들에서 좌우가 같아야 비교 가능하다. 다르면 어차피 다른것일 뿐더러 Array Error가 발생할 수도 있음.
notDiff = true; // 초기화
while(!tempSave.isEmpty()){ // 이 board블록이 다시 쓰일수도 있으니 맨뒤에 넣어줌.
AfterboardFigure.offer(tempSave.poll());
}
}else{ // XY축이 같은경우 비교해봐야겠지
int temp[][] = new int[Xleng][Yleng];
for(int i=0; i<Xleng; i++){
for(int j=0; j<Yleng; j++){
temp[i][j] = nowFigure[i][j];
}
}
for(int i=0; i<Xleng; i++){
for(int j=0; j<Yleng; j++){
if(temp[i][j] == num[i][j] && notDiff){ // 둘이 같은거라면
if(temp[i][j]==1) nowFigureSize++; // 블록 채워지는 양만큼 더해준다.
}else{
nowFigureSize = 0; // 하나라도 다르면 걍 다 없어짐
notDiff = false; // 둘은 다른블록이라고 표시
}
}
}
if(notDiff){ // 위의 for문 끝까지 같은블록이라면 같은거지
tempSave.clear(); // 이블록은 썼으니까 버림
return nowFigureSize; // 이 블록 채워진것만큼 답에 더해준다.
} else{ // 다른 블록이었다면
notDiff = true; // 초기화
while(!tempSave.isEmpty()){ // 이 블록은 후에 쓸수도 있으므로 다시 더함
AfterboardFigure.offer(tempSave.poll());
}
}
}
nowFigure = new int[11][11];
maxX = 0;
maxY = 0;
minX = 11;
minY = 11;
continue;
}
nowFigure[nowTable[0]][nowTable[1]]++;
maxX = Math.max(maxX, nowTable[0]);
minX = Math.min(minX, nowTable[0]);
maxY = Math.max(maxY, nowTable[1]);
minY = Math.min(minY, nowTable[1]);
}
return 0;
}4. 엄청 길게 설명한 이유는 이 문제의 경우는 알고리즘 자체를 생각하는게 어렵다기 보다는 얼마나 생각을 잘 전개하고 표현할 수 있는지에 관한 문제라고 생각하였기 때문이다.
- 정리하자면
-> 각각 주어진 값을 도형으로 만든다.
-> 도형은 돌려야 하는데
0 1 0
1 1 1
0 0 0
0 0 0
0 1 0
1 1 1
얘네 둘이 서로 다른 도형이다. 그러니까 비교를 잘 하기 위해서 도형으로 만들때나 이를 돌릴때 공백이 없도록 하는게 중요하다.
-> 돌리면서 비교하고 맞으면 그 도형의 크기만큼 더해줌
다구하면 완성!!
전체 코드
이거는 근데 남의 코드 봐도 별 도움 안되는것 같음...알고리즘을 생각해 보고 실제로 직접 구현하는게 도움될 것이다. 진짜로.
import java.util.*;
class Solution {
public static int Xmove[] = {-1, 1, 0, 0};
public static int Ymove[] = {0, 0, -1, 1};
public static Queue<int[]> boardFigure = new LinkedList<>();
public static Queue<int[]> tableFigure = new LinkedList<>();
public static Queue<int[]> AfterboardFigure = new LinkedList<>();
public static Queue<int[]> AftertableFigure = new LinkedList<>();
public static boolean check[][];
public static int xArea;
public static int yArea;
public static int minX;
public static int minY;
public static int maxX;
public static int maxY;
public static int boardCnt;
public static int tableCnt;
public int solution(int[][] game_board, int[][] table) {
int answer = 0;
xArea = table.length;
yArea = table.length;
// game_board쪽 도형 만들기
check = new boolean[xArea][yArea];
for(int i=0; i<xArea; i++){
for(int j=0; j<yArea; j++){
if(!check[i][j] && game_board[i][j]==0){
boardCnt = 0;
minX = xArea;
maxX = 0;
minY = yArea;
maxY = 0;
boardFigureMaker(game_board, i, j);
for(int cnt=0; cnt<boardCnt; cnt++){
int ans[] = new int[2];
ans = boardFigure.poll();
ans[0] -= minX;
ans[1] -= minY;
AfterboardFigure.offer(ans);
}
AfterboardFigure.offer(new int[]{-1, -1});
}
}
}
// table쪽 도형 만들기
check = new boolean[xArea][yArea];
for(int i=0; i<xArea; i++){
for(int j=0; j<yArea; j++){
if(!check[i][j] && table[i][j]==1){
tableCnt = 0;
minX = xArea;
maxX = 0;
minY = yArea;
maxY = 0;
tableFigureMaker(table, i, j);
for(int cnt=0; cnt<tableCnt; cnt++){
int ans[] = new int[2];
ans = tableFigure.poll();
ans[0] -= minX;
ans[1] -= minY;
AftertableFigure.offer(ans);
}
AftertableFigure.offer(new int[]{-1, -1});
}
}
}
int nowFigure[][] = new int[11][11];
int maxX = 0;
int maxY = 0;
int minX = 11;
int minY = 11;
// table도형들을 기준으로 비교할것이다.
while(!AftertableFigure.isEmpty()){
int nowTable[] = new int[2]; // X Y축 좌표를 구할 nowTable
nowTable = AftertableFigure.poll();
if(nowTable[0]==-1 && nowTable[1]==-1){
int Xleng = maxX-minX+1;
int Yleng = maxY-minY+1;
int temp[][] = new int[Xleng][Yleng];
for(int i=0; i<Xleng; i++){
for(int j=0; j<Yleng; j++){
temp[i][j] = nowFigure[i][j];
}
}
for(int num=0; num<4; num++){
temp = rotate(temp);
int compare = coordinater(temp, temp.length, temp[0].length);
if(compare!=0) answer += compare;
if(compare!=0) break;
}
nowFigure = new int[11][11];
maxX = 0;
maxY = 0;
minX = 11;
minY = 11;
continue;
}
nowFigure[nowTable[0]][nowTable[1]]++;
maxX = Math.max(maxX, nowTable[0]);
minX = Math.min(minX, nowTable[0]);
maxY = Math.max(maxY, nowTable[1]);
minY = Math.min(minX, nowTable[1]);
}
return answer;
}
public static void boardFigureMaker(int[][] game_board, int x, int y){
if(x<0 || x>=xArea || y<0 || y>=yArea) return;
if(check[x][y] || game_board[x][y]==1) return;
boardCnt++;
check[x][y] = true;
maxX = Math.max(maxX, x);
minX = Math.min(minX, x);
maxY = Math.max(maxY, y);
minY = Math.min(minY, y);
boardFigure.offer(new int[]{x, y});
for(int i=0; i<4; i++){
boardFigureMaker(game_board, x+Xmove[i], y+Ymove[i]);
}
}
public static void tableFigureMaker(int[][] table, int x, int y){
if(x<0 || x>=xArea || y<0 || y>=yArea) return;
if(check[x][y] || table[x][y]==0) return;
tableCnt++;
check[x][y] = true;
maxX = Math.max(maxX, x);
minX = Math.min(minX, x);
maxY = Math.max(maxY, y);
minY = Math.min(minY, y);
tableFigure.offer(new int[]{x, y});
for(int i=0; i<4; i++){
tableFigureMaker(table, x+Xmove[i], y+Ymove[i]);
}
}
public static int[][] rotate(int[][] m) {
int N = m.length;
int M = m[0].length;
// 돌린 크기만큼으로 생성해준다.
int[][] copyMap = new int[M][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copyMap[j][N - 1 - i] = m[i][j];
}
}
// 새로 돌린 배열로 반환해준다.
return copyMap;
}
public static int coordinater(int[][] num, int Xin, int Yin){
int nowFigureSize = 0;
int nowFigure[][] = new int[11][11];
int maxX = 0;
int maxY = 0;
int minX = 11;
int minY = 11;
boolean notDiff = true;
Queue<int[]> tempSave = new LinkedList<>();
int sizeBoard = AfterboardFigure.size();
for(int cnt=0; cnt<sizeBoard; cnt++){
int nowTable[] = new int[2];
nowTable = AfterboardFigure.poll();
tempSave.offer(nowTable);
if(nowTable[0]==-1 && nowTable[1]==-1){
int Xleng = maxX-minX+1;
int Yleng = maxY-minY+1;
if(Xleng!=Xin || Yleng!=Yin){
notDiff = true;
while(!tempSave.isEmpty()){
AfterboardFigure.offer(tempSave.poll());
}
}else{
int temp[][] = new int[Xleng][Yleng];
for(int i=0; i<Xleng; i++){
for(int j=0; j<Yleng; j++){
temp[i][j] = nowFigure[i][j];
}
}
for(int i=0; i<Xleng; i++){
for(int j=0; j<Yleng; j++){
if(temp[i][j] == num[i][j] && notDiff){
if(temp[i][j]==1) nowFigureSize++;
}else{
nowFigureSize = 0;
notDiff = false;
}
}
}
if(notDiff){
tempSave.clear();
return nowFigureSize;
} else{
notDiff = true;
while(!tempSave.isEmpty()){
AfterboardFigure.offer(tempSave.poll());
}
}
}
nowFigure = new int[11][11];
maxX = 0;
maxY = 0;
minX = 11;
minY = 11;
continue;
}
nowFigure[nowTable[0]][nowTable[1]]++;
maxX = Math.max(maxX, nowTable[0]);
minX = Math.min(minX, nowTable[0]);
maxY = Math.max(maxY, nowTable[1]);
minY = Math.min(minY, nowTable[1]);
}
return 0;
}
}'알고리즘 공부 > 위클리 챌린지' 카테고리의 다른 글
| 프로그래머스 위클리 챌린지 6주차 - java (2) | 2021.09.06 |
|---|---|
| 프로그래머스 위클리 챌린지 5주차 - java (4) | 2021.08.30 |
| 프로그래머스 위클리 챌린지 4주차 - java (0) | 2021.08.23 |
| 프로그래머스 위클리 챌린지 2주차 - java (0) | 2021.08.10 |
| 프로그래머스 위클리 챌린지 1주차 - java (0) | 2021.08.10 |