ML/AI/SW Developer

BAEK21609 상어 중학교(C++, Python)

1. 문제 설명

  • 문제 링크
  • N×N인 격자
    • 검은색 블록, 무지개 블록, 일반 블록
    • 일반 블록은 M가지 색상 존재
    • 그룹 조건
      • 인접한 블록. 인접 조건 $ \vert r1 - r2 \vert + \vert c1 - c2 \vert = 1$
      • 그룹에는 일반 블록이 적어도 하나 있어야함
      • 검은색 블록은 포함되면 안됨
      • 그룹의 최소 블록수는 2
  • 절차
    1. 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
    2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
    3. 격자에 중력이 작용한다.
    4. 격자가 90도 반시계 방향으로 회전한다.
    5. 다시 격자에 중력이 작용한다.
조건
첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.

둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.

2. 풀이

  • 시물레이션
    1. 가장 큰 블록 그룹 탐색
      • 그룹 대표 블록은 무지개 블록이 아닌 블록 중 행의 번호가 가장 작은 블록, 다음 기준은 열의 번호가 가장 작은 블록
      • BFS활용 인접 조건에 포함되는 블록들을 하나의 그룹으로 설정
      • 탐색 결과 가장 큰 그룹이 바뀌면 업데이트
      • 무지개 블록에 대한 방문여부는 초기화 해주어야함
        • 여러 그룹에 속할 수 있기 때문!
    2. 블록 제거
      • 1번에서 탐색된 그룹 제거
      • 그룹의 블록수의 제곱 만큼 점수 적용
    3. 중력 작용
      • 중력 작용
      • 주의할점: 검은색 블록은 움직이지 않는다.
    4. 회전
      • 90도 반시계방향 회전
    5. 중력 작용
      • 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++과 동일한 알고리즘으로 짰는데, 채점하자마자 틀렸다고 나오고 있다. 열심히 디버깅 중이다… 여러 테스트 케이스를 시도해보았지만 모두 통과된다. 발견하지 못한 엣지 케이스가 무엇인지 찾는 중이다.