1. 문제 링크
<백준 21609번>
https://www.acmicpc.net/problem/21609
21609번: 상어 중학교
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록
www.acmicpc.net
2. 문제 풀이
안녕하세요. 반례 찾을 때마다 시간을 엄청 날려버려서 또 찾아왔습니다.
이제는 그냥 문제 풀 때마다 글을 써야 할까 싶네요.
마침 애드센스도 승인됐고? 방문자도 많아지면?
억만장자의 길로 한 발자국 ... 은 무슨. 개발 블로그는 돈이 안됩니다. ^^;
개발 + 취미 + 일상으로 운영하면 괜찮긴 할 텐데 글쎄요.. 🧐 블로그가 주가 되면 안 될 거 같아요.
그냥 제 헛소리 적는 공간입니다. 광고를 차단하는 애드블록을 차단하는 스크립트는 넣지 않겠습니다.
(광고 눌러줬으면 좋겠다)
https://solved.ac/profile/madirony52
solved.ac
알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다.
solved.ac
(꾸준함의 어필은 solved.ac로 ...?) 라이벌 신청 환영입니다. 😌
흠흠.. 아무튼 삼성 기출 문제를 풀다 보면 상어를 자주 만나게 될 겁니다.
지금까지는 마법사 상어의 마법을 구현해줬다면 ..
이제는 육아...?
초등학교를 졸업시키면 중학교로 되돌아옵니다..
https://www.acmicpc.net/problem/21608
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
위의 문제를 푼 후에 "어?? 풀만하네??"하고 자신만만한 상태로 금방 풀 수 있을 거라 생각했는데..
망했어요.
이 문제를 바로 푸려면 정신 똑바로 차리고 조건을 꼼꼼히 본 후에 코드도 꼼꼼히 짜야합니다.
- 블록 그룹의 조건
- 일반 블록 최소 1 (그룹 내 일반 블록의 색상은 동일해야)
- 검은 블록 x (그룹 포함 불가)
- 무지개 블록 o (그룹 포함 가능)
- 크기는 2 이상
- 블록의 색상
- M가지색
- 무지개색
- 검은색
- 그룹 선정을 위한 기준 블록 선정
- 그룹의 기준 블록 : 무지개 블록이 아니면서 (행번호 최솟값 >> 열번호 최솟값)
- 블록 그룹의 선정 : 그룹의 크기 >>> 무지개 블록의 수 >> 행 > 열
최종적으로는 아래의 루틴을 반복하다가 그룹이 더 이상 존재하지 않을 때, 그동안 합한 점수를 출력하면 됩니다.
1) 기준 블록을 선정
2) 그룹의 모든 블록을 제거하고 제거한 블록의 수의 제곱만큼 점수 획득
3) 중력
4) 90도 반시계 회전
5) 중력
이 문제는 구석구석 반례를 찾는데에서 시간을 많이 잡아먹었습니다.
저 같은 경우에는,
1. 무지개 블록을 기준 블록으로 정하는 경우가 있었고,
2. bfs의 visited 배열의 무지개 블록의 위치 값을 갱신하지 않아 배열 초기화가 제대로 이루어지지 않았습니다.
처음에는 배열 입력을 받을 때, 무지개 블록 위치를 ArrayList에 받아서 고정된 위치를 계속 초기화했습니다.
이러니 프로그램이 제대로 돌아가지 않았죠.. 😡
그래서 bfs를 돌릴 때마다 Queue에 넣어주기로 했습니다.
if(arr[nx][ny] == 0) //무지개 노드 위치 저장
queue2.add(new Node(nx, ny));
그 후에 방문한 무지개 블록의 방문 값을 초기화하면 만사 OK.
//무지개 노드 방문 복구
while(!queue2.isEmpty()){
Node tmp = queue2.poll();
visited[tmp.x][tmp.y] = false;
}이런 식으로 매번 초기화해준다면 배열에 중력을 적용하든 회전을 하든 상관없겠죠?
아, 무지개 블록을 기준 값으로 잡는 문제는 조건식을 좀 더 추가해서 해결했습니다.
이러면 일반 블록만 기준 블록이 됨 ㅇㅇ..
if(!visited[i][j] && arr[i][j] != -1 && arr[i][j] != -2 && arr[i][j] != 0) {
queue.add(tmpStd = new Node(i, j));
visited[i][j] = true;
color = arr[i][j]; size++;
}
많이 지저분해 보이지만 오늘도 궁금증 해결 ~~!!
추가로 배열의 반시계 방향 90도 회전에 대해 말해보자면,
//반시계방향 배열 회전
static void rotate(){
int[][] arr2 = new int[n][n];
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
arr2[n-1-j][i] = arr[i][j];
for(int i = 0; i < n; i++)
System.arraycopy(arr2[i], 0, arr[i], 0, arr2[i].length);
}예전에 배열을 시계방향으로 90도 회전하는 알고리즘이 필요해서 구현한 적이 있었는데요.
그때는 이중 for문을 2번이나 써서 (상하반전, 대각반전) 코드가 좀 복잡했단 말이죠.
그런데 스터디를 하면서 요것을 한 줄로 처리하는 방법을 알았답니다..
어때요,, 깔끔하죠.. 그냥 for문으로 90도 꺾은 인덱스에 넣으면 됨.. 그다음 배열을 복사하면 됩니다.
이거에 관해서는 알고리즘 메뉴에서 따로 자세히 파보도록 하겠습니다.
마지막으로 중력은 그냥 끌어내리면 됩니다.
//중력
static void gravity(){
for(int i = n-2; 0 <= i; i--){
for(int j = 0; j < n; j++){
if(arr[i][j] == -2 || arr[i][j] == -1) continue;
int tmp = arr[i][j], ni = i;
while(ni+1 < n && arr[ni+1][j] == -2)
ni++;
if(arr[ni][j] == -2) {
arr[ni][j] = tmp;
arr[i][j] = -2;
}
}
}
}빈 공간이면 위에 있는 블록을 쭉- 끌어당겨서 내려놓으면 됩니다.
참 쉽 죠 ?
이번엔 특별히 주석을 조금 달아놨습니다. 구현은 코드가 많이 지저분해지는 경향이 있어서 어쩔 수 없네요.
며칠 후에 제 코드를 보고 다시 설명하라고 하면 좀 어질어질함. 그래서 조금은 달아놓으려구요.
3. 소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int[] dx = {0, -1, 1, 0};
static int[] dy = {-1, 0, 0, 1};
static int n, m, ans = 0; //ans : 최종 점수
static int[][] arr;
static boolean[][] visited;
static Queue<Node> queue = new LinkedList<>(); //bfs
static Queue<Node> queue2 = new LinkedList<>(); //무지개 블록 초기화 큐
static class Node{
int x;
int y;
Node(int x, int y){
this.x = x;
this.y = y;
}
}
static Node standard; //기준 블록 노드
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
arr = new int[n][n]; visited = new boolean[n][n];
for(int i = 0; i < n; i++){
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
//반복
while(true) {
check();
score();
gravity();
rotate();
gravity();
}
}
//반시계방향 배열 회전
static void rotate(){
int[][] arr2 = new int[n][n];
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
arr2[n-1-j][i] = arr[i][j];
for(int i = 0; i < n; i++)
System.arraycopy(arr2[i], 0, arr[i], 0, arr2[i].length);
}
//중력
static void gravity(){
for(int i = n-2; 0 <= i; i--){
for(int j = 0; j < n; j++){
if(arr[i][j] == -2 || arr[i][j] == -1) continue;
int tmp = arr[i][j], ni = i;
while(ni+1 < n && arr[ni+1][j] == -2)
ni++;
if(arr[ni][j] == -2) {
arr[ni][j] = tmp;
arr[i][j] = -2;
}
}
}
}
//점수 계산
static void score(){
int score = 0, color = arr[standard.x][standard.y];
visited = new boolean[n][n];
queue.add(standard); visited[standard.x][standard.y] = true;
while(!queue.isEmpty()){
Node tmp = queue.poll();
arr[tmp.x][tmp.y] = -2; //빈공간 : -2
score++;
for(int i = 0; i < 4; i++){
int nx = tmp.x + dx[i];
int ny = tmp.y + dy[i];
if(0 <= nx && nx < n && 0 <= ny && ny < n){
if(!visited[nx][ny] && arr[nx][ny] != -1 && arr[nx][ny] != -2){
if(color == 0 && arr[nx][ny] != 0)
color = arr[nx][ny];
if(color == arr[nx][ny] || arr[nx][ny] == 0) {
queue.add(new Node(nx, ny));
visited[nx][ny] = true;
}
}
}
}
}
ans += Math.pow(score, 2);
}
//기준 블럭 찾기
static void check(){
int max = 0, rainMax = 0; //최대 그룹 크기, 무지개 블럭 개수
visited = new boolean[n][n];
standard = new Node(-1, -1);
for(int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int size = 0, rain = 0, color = 0; Node tmpStd; //빈 공간 : -2
if(!visited[i][j] && arr[i][j] != -1 && arr[i][j] != -2 && arr[i][j] != 0) {
queue.add(tmpStd = new Node(i, j)); // 빈 공간, 무지개, 검은색 블럭은 기준 블럭x
visited[i][j] = true;
color = arr[i][j]; size++;
}
while (!queue.isEmpty()) {
Node tmp = queue.poll();
for (int k = 0; k < 4; k++) {
int nx = tmp.x + dx[k];
int ny = tmp.y + dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
if (!visited[nx][ny] && arr[nx][ny] != -1 && arr[nx][ny] != -2) {
if(color == arr[nx][ny] || arr[nx][ny] == 0) {
if(arr[nx][ny] == 0) //무지개 노드 위치 저장
queue2.add(new Node(nx, ny));
visited[nx][ny] = true;
queue.add(new Node(nx, ny));
size++;
if(arr[nx][ny] == 0) //무지개 노드 수
rain++;
}
}
}
}
}
if(max < size){
max = size; rainMax = rain; standard = new Node(i, j);
}
else if(max == size){
if(rainMax < rain){
rainMax = rain; standard = new Node(i, j);
}
else if(rainMax == rain){
if(standard.x < i)
standard = new Node(i, j);
else if(standard.x == i)
if(standard.y < j)
standard = new Node(i, j);
}
}
//무지개 노드 방문 복구
while(!queue2.isEmpty()){
Node tmp = queue2.poll();
visited[tmp.x][tmp.y] = false;
}
}
}
//그룹이 없으면 합 출력 후 프로그램 종료
if(max < 2) {
System.out.println(ans);
System.exit(0);
}
}
}
3-1. 반례
4 3
1 1 1 3
3 2 3 3
1 2 -1 3
-1 -1 1 1
----------
ans : 33
5 4
1 0 -1 0 0
2 0 -1 0 0
3 0 -1 0 0
4 0 -1 -1 -1
4 4 1 1 1
----------
ans : 58
5 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
----------
ans : 625
5 2
2 -1 -1 -1 0
-1 0 -1 1 2
-1 0 -1 0 -1
2 1 0 -1 -1
0 -1 1 2 1
----------
ans : 37 << 33일 경우 : 무지개 블록을 기준으로 했을 경우 (오답!)
4 4
2 1 4 2
4 4 0 1
1 2 3 3
-1 2 2 1
----------
ans : 33
5 4
2 3 4 -1 -1
1 -1 4 2 3
4 3 3 1 1
4 1 -1 2 2
1 1 0 -1 0
----------
ans : 29
4 5
5 2 4 4
1 5 5 2
2 4 2 -1
5 2 1 1
----------
ans : 12
6 3
1 1 1 0 0 0
1 1 1 0 0 0
1 1 3 0 0 0
0 0 0 2 2 2
0 0 0 2 2 2
0 0 0 2 2 2
----------
ans : 7934. 한줄평
백준 반례는 제 발 코드 블럭에 써주세요.
'etc. > BOJ' 카테고리의 다른 글
| [BOJ] 5373 큐빙 - Java (0) | 2024.08.09 |
|---|---|
| [BOJ] 2293 동전 1 - Java (0) | 2023.06.06 |
| [BOJ] 17142 연구소 3 - Java (0) | 2023.03.09 |
| 백준 10989번 수 정렬하기 3 (0) | 2021.08.03 |
| 백준 1152번 단어의 개수 (0) | 2021.07.23 |