- 소요시간 : 1시간 40분
- 문제 사이트 : 백준
- 문제 수준 : 골드 2
- 문제 유형 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시뮬레이션, 깊이 우선 탐색
- 다른 사람의 풀이를 참고 했는가 ? : X
- 문제 링크 : https://www.acmicpc.net/problem/21609
- 푼 날짜 : 2023.05.05
1. 사용한 자료구조 & 알고리즘
정렬, 큐, 그래프 이론, 그래프 탐색, dfs, 구현, 시뮬레이션
2. 사고과정
1. 기준 블록을 어떻게 정할 것인가?
-> 기준 블록은 그룹 블록에서 무지개 블록이 아니면서, 행이 가장 작고, 열이 가장 작은 블록이다. 이를 구할 때 애초에 그룹 블록을 탐색할 때, 무지개 블록이 아닌 색깔 블록이면서, 행, 열을 (0,0), (0,1) ... (1.0) , (1,1) ... (n-1,n-1) 로 탐색하면서 dfs를 수행하면 탐색을 시작한 위치가 기준 블록이 된다.
2. 정렬을 수행한 후 첫 번째 우선순위 그룹블록의 모든 블록을 제거해야 하는데, 그 모든 좌표는 어떻게 아나?
-> 우리는 기준 블록을 토대로 정렬하므로, 기준 블록의 위치를 기억하고 있다. 기준 블록의 위치에서 다시 dfs를 수행하면서 queue에 dfs가 수행될때마다 위치 좌표를 기억해두고, dfs가 끝나면 queue에 있는 모든 좌표의 블록들을 제거한다.
-> 중력과 반시계 방향 90도 회전은 이전에 비슷한 문제들에서 1,2번 다뤄봐서 쉬웠다.
어느 정도 설계를 마치고 코딩하는데 1시간 20분째에 모든 테스트케이스를 맞았다. 그리고 이건 틀릴 수가 없어 하고 제출했는데 1%도 안돼서 틀렸다고 나왔다. 정렬의 기준을 잘못했나, 실수한 부분이 있나 꼼꼼히 20분 정도 확인해도 이유를 모르겠어서 곰곰히 생각해봤다.
그리고 원인을 알아냈다.
dfs를 수행할 때에, 무지개 블록은 visited를 true 로 처리해 주면 안 된다. 이 무지개 블록이 다른 색깔 블록에 포함될 수 있고, 그 경우에 그룹 블록 이 더 커질 수 있다.
그렇기에 무지개 블록들의 위치는 따로 저장한 후에 dfs가 완전히 끝나고 난 후 모두 false 상태로 바꿔주어야 한다.
💬 이 작업을 해주니 바로 정답 처리!!!
3. 풀이과정
- 그룹 블록이 있는지 탐색한다. 있는 경우 while문 수행. 그룹 블록이 있는지 탐색하면서 그룹 블록 list에 그룹 블록들을 추가한다.
- dfs를 통해서 그룹 블록들을 탐색한다. 앞서 말했 듯 무지개 블록들은 따로 visit를 false로 바꿔준다.
- 그룹 블록들을 기준에 맞게 정렬한다
- 정렬된 우선 순위가 가장 높은 블록의 기준 블록을 알고 있으므로, 그 블록에서 dfs를 수행해서 queue에 해당 그룹 블록의 모든 블록들을 담고, dfs가 끝나고 모두 제거해준다. 제거한 것은 -2로 처리. 그리고 그 크기의 제곱만큼 스코어를 증가시켜준다.
- 중력을 적용시킨다.
- 반시계 방향으로 90도 회전시킨다.
- 중력을 다시 적용시킨다.
1번으로 다시 돌아감!
4. 소스코드
import java.util.*;
import java.io.*;
public class Main{
static int map[][];
static int dy[] = {-1,1,0,0};
static int dx[] = {0,0,-1,1};
static boolean visited[][];
static Queue<Integer[]> queue=new LinkedList<>();
static ArrayList<Integer[]> block=new ArrayList<>();
static int count = 0;
static int rainbow = 0;
static int score = 0;
static ArrayList<Integer[]> rainbowBlockList=new ArrayList<>();
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st=new StringTokenizer(br.readLine());
int N=Integer.parseInt(st.nextToken());
int 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());
}
}
//그룹 블록이 있는지 체크.
//체크 하면서 그룹블록을 list에 같이 넣어줌.
while(checkGroupBlock()) {
//그룹 블록들을 정렬함.
sort();
//정렬된 그룹 블록에서 첫 번째를 제거
removeBlock();
//중력이 적용
gravity();
//반시계 방향으로 90도 회전
rotate();
//다시 중력이 적용
gravity();
}
System.out.println(score);
}
//그룹 블록이 있나 체크
public static boolean checkGroupBlock() {
boolean find = false;
//이전의 그룹 블록들 제거, 방문 했는지 초기화
block.clear();
rainbowBlockList.clear();
visited=new boolean[map.length][map.length];
// 무지개 블록들이 있다면 그 위치를 list에 넣어줌
for(int i=0;i<map.length;i++) {
for(int j=0;j<map.length;j++) {
if(map[i][j] == 0) rainbowBlockList.add(new Integer[] {i,j});
}
}
for(int i=0;i<map.length;i++) {
for(int j=0;j<map.length;j++) {
count = 0;
rainbow = 0;
//해당 좌표가 색깔 블록이라면, dfs 수행.
if(map[i][j] > 0&&!visited[i][j]) {
dfs(i,j,map[i][j]);
}
//dfs 해서 count가 2 이상이 된다면, 그룹블록인 것임
if(count>1) {
//그룹블록을 발견했다는 의미로 find 는 true
find = true;
//그룹 블록의 좌표, 개수, 무지개 블록의 개수를 추가함.
block.add(new Integer[] {i,j,count,rainbow});
//무지개 블록들의 방문 처리는 false로 바꿔줌
for(int k=0;k<rainbowBlockList.size();k++) {
Integer temp[] = rainbowBlockList.get(k);
int rainbowY=temp[0];
int rainbowX=temp[1];
visited[rainbowY][rainbowX] = false;
}
}
}
}
return find;
}
//dfs 수행
public static void dfs(int y,int x,int color) {
//방문 처리
visited[y][x] = true;
// 그룹블록의 크기를 알기 위함.
count ++;
// 나중에 블록을 제거할 때 사용하기 위해 queue에 add.
queue.add(new Integer[] {y,x});
for(int i=0;i<4;i++) {
int nextY=y+dy[i];
int nextX=x+dx[i];
if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
continue;
if(visited[nextY][nextX])
continue;
//현재 색깔과 같으면 dfs수행
if(map[nextY][nextX]==color)
dfs(nextY,nextX,color);
//무지개 블록이라면 무지개 블록의 개수를 늘리고 dfs 수행
if(map[nextY][nextX]==0) {
rainbow++;
dfs(nextY,nextX,color);
}
}
}
//정렬함.
public static void sort() {
Collections.sort(block,new Comparator<>() {
@Override
public int compare(Integer n1[],Integer n2[]) {
if(n1[2]<n2[2]) return 1;
else if(n1[2]==n2[2]) {
if(n1[3]<n2[3]) return 1;
else if(n1[3] == n2 [3]) {
if(n1[0]<n2[0])
return 1;
else if(n1[0]==n2[0]) {
if(n1[1]<n2[1]) return 1;
}
}
}
return -1;
}
});
}
//그룹블록을 제거.
public static void removeBlock() {
Integer temp [] = block.get(0);
int y = temp[0];
int x = temp[1];
int size = temp[2];
queue=new LinkedList<>();
visited=new boolean[map.length][map.length];
//우선 순위 가장 높은 그룹블록에서 dfs를 수행
dfs(y,x,map[y][x]);
//점수를 더해줌
score += (size*size);
//빈 공간이라는 표시로 -2로 바꿈.
while(!queue.isEmpty()) {
Integer now[] = queue.poll();
int nowY=now[0];
int nowX=now[1];
map[nowY][nowX] = -2;
}
}
//중력이 작용
public static void gravity() {
for(int i=map.length-1;i>=0;i--) {
for(int j=0;j<map.length;j++) {
int nowY = i;
//빈 공간이거나, 검정 블록이라면 처리 X
if(map[i][j]== -2 || map[i][j] == -1)
continue;
//맵의 끝을 만나거나, 다음 좌표가 빈 칸이 아닐 때까지 탐색
while(true) {
if(nowY==map.length-1||map[nowY+1][j]!=-2) break;
nowY++;
}
//위치를 바꿔줌.
int temp = map[i][j];
map[i][j] = map[nowY][j];
map[nowY][j] = temp;
}
}
}
//반시계 방향으로 90도 회전
public static void rotate() {
int tempMap[][]=new int[map.length][map.length];
int idx1 = 0;
for(int i=map.length-1;i>=0;i--) {
int idx2 = 0;
for(int j=0;j<map.length;j++) {
tempMap[idx1][idx2] = map[j][i];
idx2++;
}
idx1++;
}
for(int i=0;i<map.length;i++) {
for(int j=0;j<map.length;j++) {
map[i][j] = tempMap[i][j];
}
}
}
}
5. 결과
무지개 블록들을 처리 안해준 것에서 2번 틀렸다.
어떤 오류가 있을까 생각했다. overflow 도 생각해봤는데, 굳이 계산을 해주지 않더라도 전혀 날 수 없는 입력의 크기였다.
6. 회고
예제 입력으로는 절대 생각해 낼 수 없는 히든 테스트케이스를 생각해내서 기쁘다.
하지만!!!!!!!!!!!
한 가지 무서운 것은 실제 시험장에선 이게 정답인지 틀렸는지 알려주지 않는 것이다. 테스트케이스만 통과했다고 오? 틀릴 수가 없는데? 하고 그대로 제출했다가는.....
✔️ 어떤 히든 테케, 반례가 있을지 생각하고, 또 생각하자 !!!
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212
