깊이/너비 우선 탐색(DFS/BFS) > 퍼즐 조각 채우기 (Level 3)

문제 링크

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

프로그래머스

 

문제 설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

• 조각은 한 번에 하나씩 채워 넣습니다.
• 조각을 회전시킬 수 있습니다.
• 조각을 뒤집을 수는 없습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

다음은 퍼즐 조각을 채우는 예시입니다.

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.

이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

• 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
• 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.

현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 3 ≤ game_board의 행 길이 ≤ 50
• game_board의 각 열 길이 = game_board의 행 길이
  • 즉, 게임 보드는 정사각 격자 모양입니다.
  • game_board의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
  • 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• table의 행 길이 = game_board의 행 길이
• table의 각 열 길이 = table의 행 길이
  • 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다.
  • table의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
  • 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• game_board에는 반드시 하나 이상의 빈칸이 있습니다.
• table에는 반드시 하나 이상의 블록이 놓여 있습니다.

 

입출력 예

 

입출력 예 설명

입출력 예 #1

입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.

입출력 예 #2

블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

 

소스 코드

struct Block
{
	int x = 0;
	int y = 0;
	Block( int row, int col )
		: x( row ), y( col )
	{
	}
	Block() = default;

	bool operator ==( Block rhs )
	{
		if( rhs.x == x && rhs.y == y )
			return true;
		return false;
	}

	bool operator !=( Block rhs )
	{
		return !( *this == rhs );
	}
};

bool CompX( Block a, Block b )
{
	return a.x < b.x;
}

bool CompY( Block a, Block b )
{
	return a.y < b.y;
}

void MoveToZeroToZeroPoint( vector<vector<Block>>& puzzles )
{
	for( int i = 0; i < puzzles.size(); ++i )
	{
		Block minBlockX = *min_element( puzzles[ i ].begin(), puzzles[ i ].end(), CompX );
		Block minBlockY = *min_element( puzzles[ i ].begin(), puzzles[ i ].end(), CompY );
		
		for( int j = 0; j < puzzles[ i ].size(); ++j )
		{
			puzzles[ i ][ j ].x -= minBlockX.x;
			puzzles[ i ][ j ].y -= minBlockY.y;
		}
	}
}

void Rotate( vector<vector<Block>>& puzzles )
{
	for( int i = 0; i < puzzles.size(); ++i )
	{
		Block maxBlockX = *max_element( puzzles[ i ].begin(), puzzles[ i ].end(), CompX );
		Block maxBlockY = *max_element( puzzles[ i ].begin(), puzzles[ i ].end(), CompY );
		int size = max( maxBlockX.x, maxBlockY.y ) + 1;
		
		for( int j = 0; j < puzzles[ i ].size(); ++j )
		{
			Block puzzle = puzzles[ i ][ j ];
			puzzles[ i ][ j ].y = puzzle.x;
			puzzles[ i ][ j ].x = size - puzzle.y - 1;
		}
	}
	MoveToZeroToZeroPoint( puzzles );
}

void DFS( int row, int col, vector<vector< bool >>& visited, vector<Block>& puzzle, const vector<vector<int>> table, int blank )
{
	if( visited[ row ][ col ] == true ) return;
	if( table[ row ][ col ] != blank )	return;

	visited[ row ][ col ] = true;
	puzzle.emplace_back( Block( col, row ) );
	int dx[ 4 ] = { 0, 0, -1, +1 };
	int dy[ 4 ] = { +1, -1, 0, 0 };
	int size = visited.size();
	for( int i = 0; i < 4; ++i )
	{
		int nx = col + dx[ i ];
		int ny = row + dy[ i ];

		if( nx < 0 || ny < 0 )				continue;
		if( nx >= size || ny >= size )		continue;
		if( table[ ny ][ nx ] != blank )	continue;

		DFS( ny, nx, visited, puzzle, table, blank );
	}
}

void Divide( const vector<vector<int>> table, vector<vector<Block>>& puzzles, int blank )
{
	int size = table.size();
	vector<vector<bool>> visited( size, vector<bool>( size, false ) );

	for( int row = 0; row < size; ++row )
	{
		for( int col = 0; col < size; ++col )
		{
			if( table[ row ][ col ] != blank ) 	continue;
			if( visited[ row ][ col ] == true ) continue;

			vector<Block> puzzle;
			DFS( row, col, visited, puzzle, table, blank );

			if( puzzle.empty() == false )
				puzzles.emplace_back( puzzle );
		}
	}
}

bool CompareBlock( vector<Block> board, vector<Block> table )
{
	int count = 0;
	for( int i = 0; i < board.size(); ++i )
	{
		for( int j = 0; j < table.size(); ++j )
		{
			if( board[ i ] == table[ j ] )
				count++;
		}
	}

	if( count == board.size() )
		return true;

	return false;
}

void Check( vector<vector<Block>>& board, vector<vector<Block>>& table )
{
	for( int i = 0; i < board.size(); ++i )
	{
		for( int j = 0; j < table.size(); ++j )
		{
			if( board[ i ].size() != table[ j ].size() )
				continue;
			if( CompareBlock( board[ i ], table[ j ] ) )
			{
				board.erase( board.begin() + i );
				table.erase( table.begin() + j );
				j = -1;
			}
		}
	}
}

int solution( vector<vector<int>> game_board, vector<vector<int>> table )
{
	int answer = -1;
	vector<vector<Block>> puzzles[ 2 ];
	
	Divide( game_board, puzzles[ 0 ], 0 );
	Divide( table, puzzles[ 1 ], 1 );
	MoveToZeroToZeroPoint( puzzles[ 0 ] );
	MoveToZeroToZeroPoint( puzzles[ 1 ] );
	
	int sum = 0;
	for( int i = 0; i < puzzles[ 1 ].size(); ++i )
	{
		for( int j = 0; j < puzzles[ 1 ][ i ].size(); ++j )
			sum++;
	}
	
	for( int i = 0; i < 4; ++i )
	{
		Check( puzzles[ 0 ], puzzles[ 1 ] );
		Rotate( puzzles[ 0 ] );
		if( puzzles[ 0 ].empty() || puzzles[ 1 ].empty() )
			break;
	}

	int count = 0;
	for( int i = 0; i < puzzles[ 1 ].size(); ++i )
	{
		for( int j = 0; j < puzzles[ 1 ][ i ].size(); ++j )
			count++;
	}
	answer = sum - count;
	return answer;
}

 

생각해 볼 것

문제를 보고 고민을 많이 했다. 이틀 정도 고민하고 내 머리속에 떠오른 방법은 아래와 같다.

1. 퍼즐을 조각별로 분해한다.
2. 원점을 기준으로 좌표이동 한다.
3. 갖고 있는 퍼즐 조각의 칸 수를 저장한다.
4. 회전 한 후, 버블 탐색으로 검사한다.
5. 일치한 경우 삭제한다.
6. 4회전 후 남아 있는 퍼즐 조각의 수와 3에서 저장한 값을 뺀다.

3번 째 입출력 예는 다른 사람이 올린 테스트 케이스다.