[BOJ 21609] 상어중학교
업데이트:
문제
- BOJ 21609
- 문제의 저작권은 Baekjoon Online Judge에 있습니다.
접근방식
문제를 푸는데는 오래 안걸렸는데 조건을 제대로 안읽어서 디버깅하는데 오래 걸렸다.
주의할 점은 3가지인데,
1) 무지개는 중복 방문 가능하므로 일반블록/무지개일때 방문배열을 따로 관리하고 초기화 시점도 다르다.(일반블록은 map돌기 전, 무지개는 그룹 만들기 전)
2) visited[][]가 필요한 이유는 상하좌우 탐색을 하기 때문에 이미 만든 그룹은 다시 만들 필요가 없다.(앞의 좌표에서 이미 만들어져있기 때문)
만약 다시 방문할 경우 기준블록이 커지는 경우가 발생할 수 있다(밑에서 위로 탐색할 때)
-1 0 0
-1 1 1
3 3 1
예를 들어 위와 같은 배열이 존재할 때 기준블록이 (2,1)이 아닌 (3,3)이 될 수 있다(기준블록은 그룹내에서 행,열이 가작 작은 일반배열이어야 하기 때문)
3) 기준블록은 반드시 그룹내에 하나이상 존재해야 하므로 일반블록일때만 findGroup()을 호출한다. 그리고 cnt는 1부터 시작한다.
접근 순서
map[][]을 돌면서 i,j일 때 만들어지는 블록을 구한다.- 상하좌우 탐색하면서 범위 안에 들고 검은블록이 아니면
- 일반블록일 경우 방문처리해주고
visited[][]배열에 표시한다. - 무지개이면
rVisited[][]에 표시하고 그 수를 카운트한다. - 현재 좌표 객체
Point p를 만들어서 임시그룹리스트tmpGroup에 넣는다. - 만들어진 개수가 2개 이상이면
tmpGroup을 최종그룹리스트pq에 넣는다.
- 1에서 최종 만든
pq에서 크기가 가장 큰 블록을 꺼내서maxGroup객체에 넣는다.pq의 타입Group클래스는 우선순위가 ‘1)블록수가 가장 많음 2)무지개수가 큼 3)기준블록의 x가 큼 4)기준블록의 y가 큼’ 으로 정렬되어있음
-
maxGroup내의 좌표 리스트list의 크기만큼 점수의 제곱값을Ans에 누적하고,map[][]에 비워준다. - 중력 진행
map[][]을 돌면서 검은블록이 아닌 블록인 경우gravity(int i, int j, int num)으로 넘겨서 블록을 아래로 이동시킨다.i의 아래값인i+1값의 범위체크,블록이 없는지 체크하고 계속 내려가기 위해 재귀호출한다.- 만약 더이상 못 내려가면 이때 이동할 좌표값을 return한다.
- return받은 좌표를
Point p에서 받아서 원래좌표는 비우고 새로운 좌표map[p.x][p.y]로 이동시킨다.
- 90도 반시계 방향으로 회전시킨다.
tmp[i][j] = map[j][N-1+1]점화식을 구해 해결한다.
- 다시 중력을 진행한다.
- 1~6번을 반복하고 블록이 더 이상 만들어지지 않는다면(
pq.size()==0) 종료하고Ans를 출력한다.
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, M;
static int[][] map;
static boolean[][] visited; //일반 방문관리
static boolean[][] rVisited; //무지개 방문관리
static PriorityQueue<Group> pq;
static Group maxGroup; // 후보 중 가장 큰 블록
static int[][] dArr = { {-1, 0}, { 1, 0 }, { 0, -1 }, { 0, 1 } }; //위로 구하면 안됨!!
static int Ans;
static class Group implements Comparable<Group> {
List<Point> list; //현재 그룹의 좌표들
int rCnt; // 무지개블록 개수
int mainX; // 기준블록의 행
int mainY; // 기준블록의 열
public Group(List<Point> p, int r, int x, int y) {
this.list = p;
this.rCnt = r;
this.mainX = x;
this.mainY = y;
}
@Override
public int compareTo(Group o) {
if(this.list.size() == o.list.size()) {
if (this.rCnt == o.rCnt) { // 1.무지개수 큰거 2.기준블록 x큰거 3.기준블록 y큰거
if (this.mainX == o.mainX) return Integer.compare(o.mainY, this.mainY);
else return Integer.compare(o.mainX, this.mainX);
} else return Integer.compare(o.rCnt, this.rCnt);
}else return Integer.compare(o.list.size(), this.list.size());
}
}
static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
} // End input
while (true) {
pq = new PriorityQueue<>();
visited = new boolean[N + 1][N + 1];
// 1. 크기가 가장 큰 블록 찾기
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (map[i][j] <= 0) continue; //일반블록만 넣기
visited[i][j] = true;
findGroup(i, j);
}
}
if (pq.size() == 0) {
System.out.println(Ans);
break; // 블록 구할 수 없으면 종료
}
// 후보들 중에서 크기 가장 큰 블록 꺼내기
maxGroup = pq.poll();
// 2. 블록그룹 제거
Ans += (int)(Math.pow(maxGroup.list.size(), 2)); // 점수 누적
for (Point p : maxGroup.list) map[p.x][p.y] = -2; // 비워줌
// 3. 중력
for (int j = 1; j <= N; j++) { // 열별로 1차원배열에 담는다.
for (int i = N - 1; i >= 1; i--) {
if (map[i][j] > -1) {
int num = map[i][j];
Point p = gravity(i, j, num); // 1,2,3,4,5처럼 꽉 찰 수도 있음
map[i][j] = -2; // 원래껀 비우고
map[p.x][p.y] = num; // 새로운 값 넣어준다.
}
}
}
// 4. 90도 반시계방향 회전
map = rotate();
// 5. 마지막 중력
for (int j = 1; j <= N; j++) { // 열별로 1차원배열에 담는다.
for (int i = N - 1; i >= 1; i--) {
if (map[i][j] > -1) {
int num = map[i][j];
Point p = gravity(i, j, num); // 1,2,3,4,5처럼 꽉 찰 수도 있음
map[i][j] = -2; // 원래껀 비우고
map[p.x][p.y] = num; // 새로운 값 넣어준다.
}
}
}
}
}
private static int[][] rotate() {
int[][] tmp = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
tmp[i][j] = map[j][N - i + 1];
}
}
return tmp;
}
private static Point gravity(int i, int j, int num) {
int ni = i + 1;
// 범위 끝이나 다른 블록을 만나면 더이상 못내려감
if (ni > N || map[ni][j] > -2) return new Point(i, j);
else return gravity(ni, j, num);
}
private static void findGroup(int nowX, int nowY) {
int color = map[nowX][nowY];
int rainbowCnt = 0;
rVisited = new boolean[N+1][N+1]; //무지개 방문관리
Queue<Point> q = new LinkedList<>();
List<Point> tmpGroup = new ArrayList<Point>();
q.add(new Point(nowX, nowY));
tmpGroup.add(new Point(nowX, nowY));
while (!q.isEmpty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
Point p = q.poll();
for (int d = 0; d < 4; d++) {
int nx = p.x + dArr[d][0];
int ny = p.y + dArr[d][1];
// 범위체크, 검은블록X
if (nx >= 1 && nx <= N && ny >= 1 && ny <= N && map[nx][ny] > -1) {
if (map[nx][ny] > 0) { //일반 블록이면
if(map[nx][ny] != color || visited[nx][ny]) continue; // 일반블록이면 컬러가 같아야함
visited[nx][ny] = true; //무지개는 중복가능
}else if(map[nx][ny] == 0) { //무지개이면
if(rVisited[nx][ny]) continue;
rVisited[nx][ny] = true;
rainbowCnt++; // 무지개 수 카운트
}
Point np = new Point(nx, ny);
tmpGroup.add(np);
q.add(np);
}
}
}
}
// 개수 2개 이상, 같거나 더 큰 블록인지 체크
if (tmpGroup.size() >= 2) {
pq.add(new Group(tmpGroup, rainbowCnt, nowX, nowY));
}
}
}