[프로그래머스(Programmers)][자바(java)] (Lv3) 3주차 - 퍼즐 조각 채우기 <위클리 챌린지>

 

https://programmers.co.kr/learn/courses/30/lessons/84021

코딩테스트 연습 - 3주차

 

 

문제 요약

 

table[][]에 있는 퍼즐 조각을 game_board[][]에 최대한으로 채워넣을 수 있는 칸의 개수 리턴

*  퍼즐 회전 가능 ( 뒤집을 수는 없음 )
*  채워 넣은 퍼즐 조각과 인접한 칸이 비어 있으면 안 됨
*  game_board의 가로 길이 = game_board의 세로길이 = table의 가로 길이 = table의 세로 길이

 

 

 

문제 풀이

 

import java.util.*;

public class Solution {

	class Cell {
		int x, y;
		Cell(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public List<boolean[][]> findBlocks(int[][] a, int o, int n) { /* BFS */ // a : array, o : value (zero or one), n : length of board
		int i, j, d, x, y, nx, ny; // d : direction, x/y : [next] x/y
		int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 }; // directions x/y
		boolean v[][] = new boolean[n][n]; // v : array to check visited cells
		List<boolean[][]> bs = new ArrayList<>(); // blocks
		List<Cell> b; // one block
		Queue<Cell> q; Cell c, nc; // q : queue, c : [next] cell
		for (i = 0; i < n; ++i) {
			for (j = 0; j < n; ++j) {
				if (a[i][j] == o && !v[i][j]) {
					b = new ArrayList<>();
					q = new ArrayDeque<>();
					c = new Cell(i, j);
					b.add(c);
					q.add(c);
					v[i][j] = true;
					while (!q.isEmpty()) {
						c = q.remove();
						x = c.x; y = c.y;
						for (d = 0; d < 4; ++d) {
							nx = x + dx[d]; ny = y + dy[d];
							if ((nx >= n || ny >= n || nx < 0 || ny < 0) || v[nx][ny])
								continue;
							if (a[nx][ny] == o) {
								nc = new Cell(nx, ny);
								b.add(nc);
								q.add(nc);
								v[nx][ny] = true;
							}
						}
					}
					bs.add(getBlockArr(b, n));
				}
			}
		}
		return bs;
	}

	public boolean[][] getBlockArr(List<Cell> b, int n) { // b : block
		int x, y, mx = n, my = n; // mx/my : minimum val of x/y
		for (Cell c : b) { // c : cell
			x = c.x; y = c.y;
			mx = mx > x ? x : mx;
			my = my > y ? y : my;
		}
		int m = 0; // m : max length of the block
		for (Cell c : b) { // c : cell
			c.x -= mx;
			c.y -= my;
			x = c.x; y = c.y;
			m = m < x ? x : m;
			m = m < y ? y : m;
		}
		m++;
		boolean bb[][] = new boolean[m][m];
		for (Cell c : b)
			bb[c.x][c.y] = true;
		return bb;
	}

	public int getBlockSize(boolean[][] b, int m) { // b : block, m : max length of the block
		int s = 0, i, j;
		for (i = 0; i < m; ++i)
			for (j = 0; j < m; ++j)
				if (b[i][j])
					s++;
		return s;
	}
	
	public boolean[][] rotateBlock(boolean[][] b, int m) { // b : block, m : max length of the block
		int mx = m, my = m, i, j;
		boolean bb[][] = new boolean[m][m]; 
		for (i = 0; i < m; ++i) {
			for (j = 0; j < m; ++j) {
				bb[i][j] = b[m - j - 1][i];
				if (bb[i][j]) {
					mx = mx > i ? i : mx;
					my = my > j ? j : my;
				}
			}
		}
		boolean bbb[][] = new boolean[m][m];
		for (i = 0; i < m; ++i)
			for (j = 0; j < m; ++j)
				if (bb[i][j])
					bbb[i-mx][j-my] = true;
		return bbb;
	}

	public boolean isSame(boolean[][] b1, boolean[][] b2, int m) { // b : block, m : max length of the block
		int i, j;
		for (i = 0; i < m; ++i)
			for (j = 0; j < m; ++j)
				if( b1[i][j] != b2[i][j] )
					return false;
		return true;
	}
	
	public int solution(int[][] game_board, int[][] table) {
		int ans = 0, n = game_board.length, m, k; // n : length of board, m : max length of the block
		List<boolean[][]> bs_b = findBlocks(game_board, 0, n), bs_t = findBlocks(table, 1, n); // bs_b/t : blocks_board/table
		Map<Integer, List<boolean[][]>> map_b = new TreeMap<>();
		Map<Integer, List<boolean[][][]>> map_t = new TreeMap<>(); boolean[][][] b_r; // b_r : block_rotated
		for (boolean[][] b : bs_b) {
			m = b.length;
			if (!map_b.containsKey(m))
				map_b.put(m, new ArrayList<>());
			map_b.get(m).add(b);
		}
		for (boolean[][] b : bs_t) {
			m = b.length;
			b_r = new boolean[4][m][m];
			b_r[0] = b;
			for (k = 1; k <= 3; ++k) {
				b = rotateBlock(b, m);
				b_r[k] = b;
			}
			if (!map_t.containsKey(m))
				map_t.put(m, new ArrayList<>());
			map_t.get(m).add(b_r);
		}
		List<boolean[][][]> puzzles; int s; // s : size of the block
		for (int mm : map_b.keySet()) { // mm : max length of the block
			loop:
			for (boolean[][] space : map_b.get(mm)) { // space : empty space( block ) of the board
				puzzles = map_t.get(mm);
				if (puzzles == null)
					continue;
				s = getBlockSize(space, mm);
				for (boolean[][][] puzzle_r : puzzles) {
					for (boolean[][] puzzle : puzzle_r) { // puzzle : puzzle of the table
						if (isSame(space, puzzle, mm)) {
							ans += s;
							puzzles.remove(puzzle_r);
							continue loop;
						}
					}
				}
			}
		}
		return ans;
	}
}

 

[ 변수명 설명 ]

   ex)

그림 1

  -   cell  :  한 칸
  -   block  :  인접한 cell들의 한 블록
  -   space  :  game_board[][] 에서의 한 블록
  -   puzzle  :  table[][] 에서의 한 블록

 

 

[ 함수 설명 ]

 

• findBlocks()  :  각 블록의 좌표들을 구함 ( spaces, puzzles 각각 )

• game_board[][] 에서는 빈공간( game_board[i][j] == 0 인 { i, j } 로부터 BFS )을 찾고, 
  table[][] 에서는 퍼즐 조각( table[i][j] == 1 인 { i, j } 로부터 BFS )을 찾아
  그 좌표들( x, y 좌표로 구성된 Cell class의 List )를 List에 넣음 ( List<Cell> b )
• 이 때 위치( x, y 좌표 ) 그대로가 아니라 기본형 배열로 바꾼 후 넣음 ( boolean[][] )
• 퍼즐들의 각 좌표 배열을 담은 리스트 리턴 ( List<boolean[][]> bs )

      ex)  위의 '그림 1'에서
          ■  노란색 space 블럭의 좌표들은 [[3,2],[4,1],[4,2],[4,3]]
          ■  초록색 puzzle 블럭의 좌표들은 [[2,1],[1,2],[2,2],[3,2]]

 

• getBlockArr()  :  한 블록의 좌표들의 리스트( List<Cell> b )를 전달 받아 기본형 배열( boolean[][] b )을 리턴함
  ( 기본형이라는 것은 블록의 위치에 상관 없이 같은 블록인지 비교할 수 있게끔 전처리 한 것을 의미 )

• 한 블록을 구성하는 셀의 좌표들에서 x, y의 각각의 최솟값( int mx, my )을 구하여 좌표값에서 뺌
• 가로 세로 통틀어 가장 큰 값( int m )을 구해 정사각형 모양의 퍼즐 배열 생성

      ex)  위의 '그림 1'에서
          ■  노란색 블럭의 기본형 좌표들은 [[0,1],[1,0],[1,1],[1,2]]  ( mx는 3, my는 1 )
          ■  초록색 블럭의 기본형 좌표들은 [[0,1],[1,0],[1,1],[2,1]]  ( mx는 1, my는 1 )

 

• rotateBlock()  :  한 블록( boolean[][] b )을 90도로 회전하고 좌표들의 기본형을 구함

• boolean bb[][] 2차원 배열을 새로 생성함( 가로&세로 길이는 블록에서 가장 긴 길이( int m )가 됨 )
• 그 2차원 배열을 90도로 회전( boolean[][] bb ) 후 기본형 배열( boolean[][] bbb )로 만듦
  

      ex)  위의 '그림 1'에서
          ■  초록색 블럭을 90도로 회전한 블록의 기본형 좌표들은 [[0,1],[1,0],[1,1],[1,2]]

      ex)  다른 예로 [[0,3],[1,3],[2,0],[2,1],[2,2],[2,3]] 로 구성된 블록
          ■  회색 블럭을 90도로 회전한 블록의 기본형 좌표들은 [[0,0],[1,0],[2,0],[3,0],[3,1],[3,2]]

 

• isSame()  :  입력받은 두 블록의 모양이 일치하는지 판단

• 두 블록을 구성하는 좌표 배열의 값이 모두 같으면 두 블록은 모양이 일치함

      ex)  위의 '그림 1'에서
          ■  노란색 블럭의 모양과  ■  초록색 블럭을 90도로 회전한 블록의 모양이 일치함

 

• solution()

• game_board[][] 에서 findBlocks()를 통해 spaces( blocks )들을 구한 것을 담은 List<boolean[][]> bs_b,
  table[][] 에서 findBlocks()를 통해 puzzles( blocks )들을 구한 것을 담은 List<boolean[][]> bs_t 을 생성
  
• Map<Integer, List<boolean[][]>> map_b 생성 후, bs_b 탐색하며 한 변의 길이가 m( key )인 블록들( value )를 담고,
  Map<Integer, List<boolean[][][]>> map_t 생성 후, bs_t 탐색하며 한 변의 길이가 m( key )인 블록들( value )
  ( + rotateBlock() 로 회전한 모양 포함 ) 를 담음
  
• map_b을 탐색하면서 한 space( block )에 대해 map_t을 탐색하며 puzzle( block ) 하나 당 3번 회전 시킨 총 4개의 모양을 isSame() 함수를 통해 비교하고, 일치하면 ans += s ( 블록의 칸 수 )

      ex)  위의 '그림 1'에서
           색칠된 board, table에서의 각각의 block( ■ space, ■ puzzle )에 대해 map_b, map_t에 각각 넣은 결과