백준 - 상어 중학교 (21609) : JAVA
문제 유형
bfs, 구현
풀이 방법 도출
문제의 조건은 다음과 같습니다.
1. 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다.
2. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다.
3. 블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 속한 블록의 개수는 2보다 크거나 같아야 한다.
4. 오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.
a. 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
b. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
c. 격자에 중력이 작용한다.
d. 격자가 90도 반시계 방향으로 회전한다.
e. 다시 격자에 중력이 작용한다.
5. 격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.이 문제는 가중치가 동일한 그래프이기 때문에, bfs를 통해서 해결할 수 있습니다.
class Group {
int r;
int c;
boolean[][] vis;
int area;
int rainbowArea;
Group(int r, int c, boolean[][] vis, int area, int rainbowArea) {
this.r = r;
this.c = c;
this.vis = vis;
this.area = area;
this.rainbowArea = rainbowArea;
}
}
class Node {
int r;
int c;
Node (int r, int c) {
this.r = r;
this.c = c;
}
}Group 클래스와 Node 클래스를 선언해줬습니다.
Group 클래스는 블록 그룹을 나타냅니다.
Node 클래스는 bfs를 위한 클래스입니다.
static boolean run() {
List<Group> groups = new ArrayList<>();
globalVis = new boolean[n][n];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (map[i][j] >= 1 && map[i][j] <= m && !globalVis[i][j]) {
Group group = bfs(i,j);
if (group.area >= 2) groups.add(group);
}
}
}
if (groups.isEmpty()) return false;
groups.sort((n1,n2)-> {
if (n1.area != n2.area) return n2.area - n1.area;
if (n1.rainbowArea != n2.rainbowArea) return n2.rainbowArea - n1.rainbowArea;
if (n1.r != n2.r) return n2.r - n1.r;
return n2.c - n1.c;
});
Group target = groups.get(0);
result += target.area * target.area;
clean(target.vis);
down();
rotate();
down();
return true;
}오토플레이를 실행하는 run 메서드입니다.
static Group bfs(int r, int c) {
boolean[][] vis = new boolean[n][n];
vis[r][c] = true;
globalVis[r][c] = true;
Queue<Node> q = new ArrayDeque<>();
q.add(new Node(r,c));
int area = 0;
int rainbowArea = 0;
while(!q.isEmpty()) {
Node cur = q.poll();
area++;
if (map[cur.r][cur.c] == 0) rainbowArea++;
for (int dir=0; dir<4; dir++) {
int nr = cur.r + dr[dir];
int nc = cur.c + dc[dir];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (vis[nr][nc]) continue;
if (map[nr][nc] != 0 && map[nr][nc] != map[r][c]) continue;
vis[nr][nc] = true;
globalVis[nr][nc] = true;
q.add(new Node(nr,nc));
}
}
return new Group(r,c,vis,area,rainbowArea);
}bfs 메서드는 위와 같습니다. 일반적인 bfs 알고리즘과 같지만, 본인과 같은 일반 블록이 아니더라도 무지개 블록(0)이라면 이동할 수 있음을 주의해야합니다.
무지개 블록이 존재하기 때문에, 각 블록 그룹의 영역이 겹칠 수 있습니다. 이 때문에 vis과 globalVis을 분리해줬습니다.
globalVis을 통해 중복으로 bfs를 수행하지 않도록합니다.
static void clean(boolean[][] vis) {
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (vis[i][j]) {
map[i][j] = -2;
}
}
}
}
clean 메서드는 위와 같습니다. 우선순위가 가장 큰 블록 그룹의 모든 블록을 제거합니다.
static void down() {
Deque<Integer> q = new ArrayDeque<>();
for (int c=0; c<n; c++) {
for (int r=0; r<n; r++) {
if (map[r][c] == -1) {
int tempR = r-1;
while (!q.isEmpty()) {
map[tempR--][c] = q.pollLast();
}
}
else {
if (map[r][c] == -2) q.addFirst(map[r][c]);
else q.addLast(map[r][c]);
}
}
int tempR = n-1;
while (!q.isEmpty()) {
map[tempR--][c] = q.pollLast();
}
}
}격자의 중력을 작용하는 down 메서드입니다. Deque 자료구조를 사용해서 구현했습니다.
static void rotate() {
int[][] tempMap = new int[n][n];
int offset = n-1;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
tempMap[Math.abs(j-offset)][i] = map[i][j];
}
}
map = tempMap;
}반시계 방향 회전을 수행하는 rotate 메서드 입니다.
시간 복잡도
O(N^4)
코드
import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
class Group {
int r;
int c;
boolean[][] vis;
int area;
int rainbowArea;
Group(int r, int c, boolean[][] vis, int area, int rainbowArea) {
this.r = r;
this.c = c;
this.vis = vis;
this.area = area;
this.rainbowArea = rainbowArea;
}
}
class Node {
int r;
int c;
Node (int r, int c) {
this.r = r;
this.c = c;
}
}
class Main {
static int[] dr = {1,-1,0,0};
static int[] dc = {0,0,1,-1};
static int n, m, result;
static int[][] map;
static boolean[][] globalVis;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n][n];
for (int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for (int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
while(true) {
if (!run()) break;
}
System.out.println(result);
}
static boolean run() {
List<Group> groups = new ArrayList<>();
globalVis = new boolean[n][n];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (map[i][j] >= 1 && map[i][j] <= m && !globalVis[i][j]) {
Group group = bfs(i,j);
if (group.area >= 2) groups.add(group);
}
}
}
if (groups.isEmpty()) return false;
groups.sort((n1,n2)-> {
if (n1.area != n2.area) return n2.area - n1.area;
if (n1.rainbowArea != n2.rainbowArea) return n2.rainbowArea - n1.rainbowArea;
if (n1.r != n2.r) return n2.r - n1.r;
return n2.c - n1.c;
});
Group target = groups.get(0);
result += target.area * target.area;
clean(target.vis);
down();
rotate();
down();
return true;
}
static void rotate() {
int[][] tempMap = new int[n][n];
int offset = n-1;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
tempMap[Math.abs(j-offset)][i] = map[i][j];
}
}
map = tempMap;
}
static void down() {
Deque<Integer> q = new ArrayDeque<>();
for (int c=0; c<n; c++) {
for (int r=0; r<n; r++) {
if (map[r][c] == -1) {
int tempR = r-1;
while (!q.isEmpty()) {
map[tempR--][c] = q.pollLast();
}
}
else {
if (map[r][c] == -2) q.addFirst(map[r][c]);
else q.addLast(map[r][c]);
}
}
int tempR = n-1;
while (!q.isEmpty()) {
map[tempR--][c] = q.pollLast();
}
}
}
static void clean(boolean[][] vis) {
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (vis[i][j]) {
map[i][j] = -2;
}
}
}
}
static Group bfs(int r, int c) {
boolean[][] vis = new boolean[n][n];
vis[r][c] = true;
globalVis[r][c] = true;
Queue<Node> q = new ArrayDeque<>();
q.add(new Node(r,c));
int area = 0;
int rainbowArea = 0;
while(!q.isEmpty()) {
Node cur = q.poll();
area++;
if (map[cur.r][cur.c] == 0) rainbowArea++;
for (int dir=0; dir<4; dir++) {
int nr = cur.r + dr[dir];
int nc = cur.c + dc[dir];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (vis[nr][nc]) continue;
if (map[nr][nc] != 0 && map[nr][nc] != map[r][c]) continue;
vis[nr][nc] = true;
globalVis[nr][nc] = true;
q.add(new Node(nr,nc));
}
}
return new Group(r,c,vis,area,rainbowArea);
}
}
cs/ps