1. 문제 설명
- 문제 링크
- N×N인 격자
- 검은색 블록, 무지개 블록, 일반 블록
- 일반 블록은 M가지 색상 존재
- 그룹 조건
- 인접한 블록. 인접 조건 $ \vert r1 - r2 \vert + \vert c1 - c2 \vert = 1$
- 그룹에는 일반 블록이 적어도 하나 있어야함
- 검은색 블록은 포함되면 안됨
- 그룹의 최소 블록수는 2
- 절차
- 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
- 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
- 격자에 중력이 작용한다.
- 격자가 90도 반시계 방향으로 회전한다.
- 다시 격자에 중력이 작용한다.
조건
첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.
둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.
2. 풀이
- 시물레이션
- 가장 큰 블록 그룹 탐색
- 그룹 대표 블록은 무지개 블록이 아닌 블록 중 행의 번호가 가장 작은 블록, 다음 기준은 열의 번호가 가장 작은 블록
- BFS활용 인접 조건에 포함되는 블록들을 하나의 그룹으로 설정
- 탐색 결과 가장 큰 그룹이 바뀌면 업데이트
- 무지개 블록에 대한 방문여부는 초기화 해주어야함
- 여러 그룹에 속할 수 있기 때문!
- 블록 제거
- 1번에서 탐색된 그룹 제거
- 그룹의 블록수의 제곱 만큼 점수 적용
- 중력 작용
- 중력 작용
- 주의할점: 검은색 블록은 움직이지 않는다.
- 회전
- 90도 반시계방향 회전
- 90도 반시계방향 회전
- 중력 작용
- 3번과 동일
- 가장 큰 블록 그룹 탐색
3. 코드
- c++
#define _CRT_NO_SECURE_WARNINGS
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
// NxN 맵크기
// M 원석 색상 종류
// -1: 검은색 블록, 0: 무지개 블록, 1~M: 색상블록
int N, M;
bool visited[20][20]; // 가장 큰 블럭 탐색용
int map[20][20]; // 맵정보
int MAX_size; // 가장 큰 블럭 크기
// 블럭 정보
struct Block {
int x, y;
int n_rainbow;
vector<pair<int, int>> path;
Block() {};
Block(int x, int y, int n_rainbow) : x(x), y(y), n_rainbow(n_rainbow) { path.clear(); };
};
Block big;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
bool path_sorting(pair<int,int> a, pair<int,int> b) {
if (a.first < b.first) return true;
else if (a.first == b.first) {
if (a.second < b.second) return true;
}
return false;
}
// 가장 큰 블럭 탐색
void Bfs(int x, int y, int c) {
queue<pair<int, int>> q;
q.push(make_pair(x, y));
visited[x][y] = true;
int temp_size = 1; // 시작점 보석
// 무지개는 방문 표시 해제 필요
vector<pair<int, int>> rainbow;
// 블록 삭제를 위한 경로 저장
vector<pair<int, int>> path;
// 보석 기준 지점을 위한 경로 저장
vector<pair<int, int>> Ex_rainbow_path;
Ex_rainbow_path.push_back(make_pair(x, y));
path.push_back(make_pair(x, y));
while (!q.empty()) {
// 현재 좌표
int cx = q.front().first;
int cy = q.front().second;
q.pop();
// 주변 탐색
for (int i = 0; i < 4; i++) {
// 주변 좌표
int nx = cx + dx[i];
int ny = cy + dy[i];
// 맵 밖으로 나가면 안됨
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
// 이미 방문했거나, 빈칸이거나, 검은색이면 처리할 필요 없음
if (visited[nx][ny] || map[nx][ny] == -2 || map[nx][ny] == -1) continue;
// 같은 색상이거나 무지개 색상이면 진행
if (map[nx][ny] == c || map[nx][ny] == 0) {
// 무지개 색상이면 나중에 초기화를 위해 좌표 저장
if (map[nx][ny] == 0) rainbow.push_back(make_pair(nx, ny));
if (map[nx][ny] != 0) Ex_rainbow_path.push_back(make_pair(nx, ny));
path.push_back(make_pair(nx, ny));
// 방문표시
visited[nx][ny] = true;
// 크기증가
temp_size++;
q.push(make_pair(nx, ny));
}
}
}
if (path.size() < 2) return;
sort(Ex_rainbow_path.begin(), Ex_rainbow_path.end(), path_sorting);
// 현재 탐색된 보석의 크기
Block temp = Block(Ex_rainbow_path[0].first, Ex_rainbow_path[0].second, rainbow.size());
temp.path = path;
// 더크면 현재 보석으로 교체
if (temp_size > MAX_size) {
MAX_size = temp_size;
big = temp;
}// 크기가 같으면
else if(temp_size == MAX_size){
// 무지개 수가 더 많은 것으로 교체
if (temp.n_rainbow > big.n_rainbow) {
big = temp;
}// 무지개 수가 같으면
else if (temp.n_rainbow == big.n_rainbow) {
// 행좌표가 더 큰것으로 교체
if (temp.x > big.x) {
big = temp;
}// 행좌표가 같으면
else if (temp.x == big.x) {
// 열좌표가 큰것으로 교체
if (temp.y > big.y) {
big = temp;
}
}
}
}
// 무지개색은 다음 블럭탐색시 중복방문이 가능함으로 방문표시 해제
for (int i = 0; i < rainbow.size(); i++) {
visited[rainbow[i].first][rainbow[i].second] = false;
}
}
void Delete() {
// big.path에 저장되어 있는 블럭들 삭제
for (int i = 0; i < big.path.size(); i++) {
map[big.path[i].first][big.path[i].second] = -2;
}
}
void Gravity() {
for (int j = 0; j < N; j++) {
for (int i = N - 1; i >= 0; i--) {
// 검은색은 안움직임
if (map[i][j] == -1) continue;
// 빈칸이면
if (map[i][j] == -2) {
int idx = i;
// 바로 위 검은색이 아닌 색상블록을 찾아서
while (map[idx][j] != -1 && map[idx][j] == -2 && idx>0) idx--;
if (map[idx][j] != -1) {
// 위치 교환
map[i][j] = map[idx][j];
map[idx][j] = -2;
}
}
}
}
}
void Rotation() {
// 테두리 개수 (회전할 사각형 개수)
int squar_num = N - 2;
int len = N - 1;
for (int i = 0; i < squar_num; i++) {
// 사각형의 시작 좌표와 끝좌표
int start_x = 0 + i;
int start_y = 0 + i;
int end_x = N - 1 - i;
int end_y = N - 1 - i;
int temp[20];
// 회전
for (int k = 0; k < len; k++) temp[k] = map[start_x][start_y + k];
for (int k = 0; k < len; k++) map[start_x][start_y + k] = map[start_x + k][end_y];
for (int k = 0; k < len; k++) map[start_x + k][end_y] = map[end_x][end_y - k];
for (int k = 0; k < len; k++) map[end_x][end_y - k] = map[end_x - k][start_y];
for (int k = 0; k < len; k++) map[end_x - k][start_y] = temp[k];
len -= 2;
}
}
void Print() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << map[i][j] << "\t";
}
cout << endl;
}
cout << endl;
}
int main() {
// 기본정보 입력
cin >> N >> M;
// 맵정보 입력
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
}
}
int answer = 0;
while (true) {
// 1. 가장 큰 블록 탐색
memset(visited, false, sizeof(visited));
big = Block(-1, -1, 0);
MAX_size = 0;
// 행이 가장 큰거, 열이 가장 큰거임으로
// 오른쪽 아래부터 탐색
for (int i = N-1; i >= 0; i--) {
for (int j = N-1; j >= 0; j--) {
// 빈칸이나 검은색은 넘기기
if (map[i][j] == -2 || map[i][j] == -1) continue;
// 무지개 거나 이미 방문한 건 넘기기
if (map[i][j] == 0 || visited[i][j]) continue;
Bfs(i, j, map[i][j]);
}
}
// 더이상 탐색되는 보석이 없으면 종료
if (big.x == -1) break;
// 2. 보석제거
answer += (big.path.size() * big.path.size());
Delete();
// 3. 중력작용
Gravity();
// 4. 회전
Rotation();
// 5. 중력작용
Gravity();
}
cout << answer << endl;
return 0;
}
- python
- 알고리즘은 동일
from collections import deque
# 탐색 시작 좌표 x, y
# 탐색 시작 블록 색깔 c
def search_block_group(x, y, c, grid, visited):
global N
global max_group
# 4방향 탐색
dx = [0,0,-1,1]
dy = [1,-1,0,0]
q = deque()
# 시작 좌표 큐에 삽입
q.append([x, y])
# 시작 좌표 방문 표시
visited[x][y] = True
# 탐색할 블록 그룹 크기(현재블록 포함시작임으로 1)
curr_size = 1
# 무지개 블록 방문 표시 해제
rainbow_block_list = []
# 대표보석을 찾기 위한 리스트
except_rainbow_block_list = [[x, y]]
# 이후 블록 제거를 위한 블록 리스트
blocks_list = [[x, y]]
# 탐색시작
while q:
cx, cy = q.popleft()
for dir in range(4):
# 주변 좌표
nx = cx + dx[dir]
ny = cy + dy[dir]
# 맵밖으로 나가면 안됨
if 0 <= nx < N and 0 <= ny < N:
# 방문했거나, 빈칸, 검은색이면 진행 x
if visited[nx][ny] or grid[nx][ny] == -2 or grid[nx][ny] == -1:
continue
# 같은 색상이거나 무지개 블록이면 진행
if(grid[nx][ny] == c or grid[nx][ny] == 0):
if grid[nx][ny] == 0:
# 무지개 블록이면 무지개 블록 리스트에 삽입
rainbow_block_list.append([nx, ny])
else:
# 무지개 블록이 아니면, 무지개 블록 제외 리스트에 삽입
except_rainbow_block_list.append([nx, ny])
# 전체 블록리스트에도 삽입
blocks_list.append([nx, ny])
# 방문표시
visited[nx][ny] = True
# 블록 그룹 크기 증가
curr_size += 1
q.append([nx, ny])
# 탐색종료(시작 탐색 위치에서 찾을 수 있는 가장 큰 블록 크기)
# 정렬(행, 열 기준 오름차순)
sorted(except_rainbow_block_list)
# 그룹 크기가 2가 안되면 빈 리스트 반환
if len(blocks_list) < 2: return []
temp_group = {
'size': curr_size,
'list': blocks_list,
'rainbow_num': len(rainbow_block_list),
'x' : except_rainbow_block_list[0][0],
'y' : except_rainbow_block_list[0][1]
}
# 현재 그룹의 크기가 더 크면 변경
if max_group['size'] < temp_group['size']:
max_group = temp_group
# 크기가 같으면
elif max_group['size'] == temp_group['size']:
# 무지개 블록 수
if max_group['rainbow_num'] < temp_group['rainbow_num']:
max_group = temp_group
elif max_group['rainbow_num'] == temp_group['rainbow_num']:
# 행기준으로
if max_group['x'] < temp_group['x']:
max_group = temp_group
# 행도 같으면
elif max_group['x'] == temp_group['x']:
# 열기준으로 판별
if max_group['y'] < temp_group['y']:
max_group = temp_group
# 무지개색 블록은 중복 방문이 가능하기 때문에 방문 표시 해제
for rainbow_x, rainbow_y in rainbow_block_list:
visited[rainbow_x][rainbow_y] = False
# 블록 그룹 제거
def delete_block(grid):
for x, y in max_group['list']:
grid[x][y] = -2
# 중력 작용
def apply_gravity(grid):
global N
for y in range(N):
for x in range(N-1, -1, -1):
# 검은색은 안움직임
if grid[x][y] == -1: continue
# 빈칸이면
if grid[x][y] == -2:
idx = x
# 위쪽으로 검은색이 아닌 색상블록을 찾아기
while grid[idx][y] != -1 and grid[idx][y] == -2 and idx > 0:
idx -= 1
# 찾았으면 위치 교환(값 변경)
if grid[idx][y] != -1:
grid[x][y] = grid[idx][y] # 해당 블록 값으로
grid[idx][y] = -2 # 빈칸으로
# 회전
def rotate_block(grid):
global N
square_num = N - 2 # 회전할 사각형 개수
length = N - 1 # 회전할 사각형 한변의 길이
for sq in range(square_num):
start_x = 0 + sq
start_y = 0 + sq
end_x = N - 1 - sq
end_y = N - 1 - sq
temp = [0 for _ in range(20)]
# 첫 테두리 복사해두기
for idx in range(length):
temp[idx] = grid[start_x][start_y + idx]
# 첫 테두리로 회전한 테두리값 옮기기
for idx in range(length):
grid[start_x][start_y + idx] = grid[start_x + idx][end_y]
# 두번째 테두리
for idx in range(length):
grid[start_x + idx][end_y] = grid[end_x][end_y - idx]
# 세번째 테두리
for idx in range(length):
grid[end_x][end_y - idx] = grid[end_x - idx][start_y]
# 마지막 테두리에 복사해 두었던 값 옮기기
for idx in range(length):
grid[end_x - idx][start_y] = temp[idx]
length -= 2 # 사각형이 줄어들면 한변의 길이가 2 줄어든다
# Main
# N 값 입력
N, M = map(int, input().split())
# grid 정보 입력
grid = [list(map(int, input().split())) for _ in range(N)]
answer = 0
while True:
# max group 초기화
max_group = {'size': 0, 'list': [], 'x': -1, 'y': -1}
# visited 초기화
visited = [[False for _ in range(N)] for __ in range(N)]
# 1. 가장 큰 블록 탐색
# 큰거로 찾으니까 큰 좌표 부터 탐색
for x in range(N-1, -1, -1):
for y in range(N-1, -1, -1):
# 빈칸이나 검은색, 무지개색 또는 방문한 블럭은 넘기기
if grid[x][y] == -2 or grid[x][y] == -1 or grid[x][y] == 0 or visited[x][y]:
continue
search_block_group(x, y, grid[x][y], grid, visited)
# 만족하는 group를 못찾으면 종료
if max_group['x'] == -1:
break
# 2. 보석제거
answer += (len(max_group['list']) ** 2) # 점수 증가
delete_block(grid)
# 3. 중력작용
apply_gravity(grid)
# 4. 회전
rotate_block(grid)
# 5. 중력작용
apply_gravity(grid)
print(answer)
4. 결과
python 연습.
C++과 동일한 알고리즘으로 짰는데, 채점하자마자 틀렸다고 나오고 있다. 열심히 디버깅 중이다…
여러 테스트 케이스를 시도해보았지만 모두 통과된다. 발견하지 못한 엣지 케이스가 무엇인지 찾는 중이다.