https://school.programmers.co.kr/learn/courses/30/lessons/84021
📕 문제 설명
주어진 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 올려놓는다. 이때, 다음 규칙을 따라 퍼즐을 채운다.
1. 조각은 한 번에 하나씩 채우기
2. 조각 회전 가능
3. 조각 뒤집기 불가능
4. 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비지 않아야 함
규칙에 맞춰 채워 넣을 때 최대로 채울 수 있는 칸 반환하기
-
Input
현재 게임 보드 상태 game_board, 테이블 위 놓인 퍼즐 조각 상태 table -
Output
최대 채울 수 있는 칸 수
예제
시도 1
(+ 파이썬에서는 리스트 좌표 추가 식으로 했을 때 통과 되는것 확인)
원래 리스트에 좌표 추가하는 식으로 했다가 리스트 비교가 안되어서 string으로 바꿨더니 일부 테케가 통과되지 않았다.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
private int n;
public int solution(int[,] game_board, int[,] table) {
int answer = 0;
n = game_board.GetLength(0);
// blank 좌표를 string으로 이어붙여서 나타냄 (blank 0들의 좌표를 string 형태로 이어 붙인 값)
List<string> blank = new List<string>();
int[] temp = new int[2] {0, 0};
// game_board 빈칸 좌표를 구해서 0,0 좌표를 기준으로 옮기기
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(game_board[i,j] == 0) // 빈칸이면
{
// 이어진 빈칸들 구하기 (즉, 퍼즐 들어갈 공간) -> (0,0) 좌표로 옮기기
blank.Add(GetPos(game_board, i, j, temp, 0));
}
}
}
string block = "";
int[,] copy_table = new int[n,n];
// table에서 퍼즐 찾고, 회전시켜 보며 game_board에서 구한 위치에 부합하는 거 있는지 찾기
for(int k = 0; k < 4; k++) // 4방향 회전
{
table = rotate(table); // 90도씩 회전
copy_table = (int[,])table.Clone();
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(copy_table[i,j] == 1)
{
block = GetPos(copy_table, i, j, temp, 1);
if(blank.Contains(block))
{
blank.Remove(block);
answer += block.Length / 2;
table = (int[,])copy_table.Clone(); // 해당 블록 방문처리된 테이블로 교체
}
else
{
copy_table = (int[,])table.Clone(); // 이번 턴의 방문 표시 없던 상태로
}
}
}
}
}
return answer;
}
// 보드, 현재 x, 현재 y, , 크기, 몇 번을 타고 갈것
public string GetPos(int[,] board, int x, int y, int[] pos, int num)
{
int[] deltaX = new int[] {-1,0,1,0};
int[] deltaY = new int[] {0,1,0,-1};
board[x,y] = 2; // 방문 표시
string result = pos[0].ToString() + pos[1].ToString();
for(int i = 0; i < 4; i++)
{
int newX = x + deltaX[i];
int newY = y + deltaY[i];
// 범위 내에서 이어진 부분 이라면
// 게임 보드: 0 찾기 , 테이블: 1 찾기
if(newX >= 0 && newY >= 0 && newX < n && newY < n && board[newX,newY] == num)
{
// 결국 현재 기준 몇 칸 갔는 지를 보면 위치 상관없이 이어진거에 초점 둘 수 있음!
int[] temp = new int[2] {pos[0] + deltaX[i], pos[1] + deltaY[i]};
result += GetPos(board, newX, newY, temp, num);
}
}
return result;
}
public int[,] rotate(int[,] table)
{
int[,] rotated = new int[n,n];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
rotated[j,n-i-1] = table[i,j];
}
}
return rotated;
}
}
시도 2
다시 리스트로 돌아와서 각 요소 비교하는 식으로 바꿨는데 로그 찍어보니 리스트 내부 요소인 int[] 자체의 같음도 판단 못하는것같다..
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int solution(int[,] game_board, int[,] table) {
int answer = 0;
int n = game_board.GetLength(0);
List<List<int[]>> blank = new List<List<int[]>>();
int[] temp = new int[2];
temp[0] = temp[1] = 0;
// game_board 빈칸 좌표를 구해서 0,0 좌표를 기준으로 옮기기
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(game_board[i,j] == 0) // 빈칸이면
{
// 이어진 빈칸들 구하기 (즉, 퍼즐 들어갈 공간) -> (0,0) 좌표로 옮기기
blank.Add(DFS(game_board, i, j, temp, n, 0));
}
}
}
List<int[]> block = new List<int[]>();
List<List<int[]>> blockList = new List<List<int[]>>();
int[,] copy_table = new int[n,n];
// table에서 퍼즐 찾고, 회전시켜 보며 game_board에서 구한 위치에 부합하는 거 있는지 찾기
for(int k = 0; k < 4; k++) // 4방향 회전
{
table = rotate(table); // 90도씩 회전
copy_table = (int[,])table.Clone();
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(copy_table[i,j] == 1)
{
block = DFS(copy_table, i, j, temp, n, 1);
bool isBlockContained = false;
foreach (var blankPos in blank)
{
if (blankPos.Count != block.Count) continue;
if (blankPos.Intersect(block).ToList().Count == block.Count)
{
blank.Remove(block);
answer += block.Count;
table = (int[,])copy_table.Clone();
isBlockContained = true;
break;
}
}
if (isBlockContained == false) copy_table = (int[,])table.Clone();
}
}
}
}
return answer;
}
// 보드, 현재 x, 현재 y, , 크기, 몇 번을 타고 갈것
public List<int[]> DFS(int[,] board, int x, int y, int[] pos, int n, int num)
{
int[] deltaX = new int[] {-1,0,1,0};
int[] deltaY = new int[] {0,1,0,-1};
board[x,y] = 2; // 방문 표시
List<int[]> result = new List<int[]>();
result.Add(pos);
for(int i = 0; i < 4; i++)
{
int newX = x + deltaX[i];
int newY = y + deltaY[i];
// 범위 내에서 이어진 부분 이라면
// 게임 보드: 0 찾기 , 테이블: 1 찾기
if(newX >= 0 && newY >= 0 && newX < n && newY < n && board[newX,newY] == num)
{
int[] temp = new int[2];
temp[0] = pos[0] + deltaX[i]; // 결국 현재 기준 몇 칸 갔는 지를 보면 위치 상관없이 이어진거에 초점 둘 수 있음!
temp[1] = pos[1] + deltaY[i];
List<int[]> tempRes = new List<int[]>();
tempRes = DFS(board, newX, newY, temp, n, num); // dfs 돌아서 연결된 부분 찾기
foreach(var a in tempRes)
{
result.Add(a);
}
}
}
return result;
}
public int[,] rotate(int[,] table)
{
int n = table.GetLength(0);
int[,] rotated = new int[n,n];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
rotated[j,n-i-1] = table[i,j];
}
}
return rotated;
}
}
하나씩 심어 나가는 개발 농장🥕 (블로그 이전중)