문제 링크 - https://www.acmicpc.net/problem/2573
🌱 문제
🌱 풀이
- 문제에서 요구하는 그대로 구현하면 되는 문제였다.
- 함수 하나 당 하나의 기능을 하도록 나눴더니 함수가 좀 많아졌다.
- 시뮬레이션하는 반복문 안에서 아래과정 반복
- 두 덩어리 이상으로 분리되기 전에 다 녹았는지 확인 ->
melt 함수
- 빙산 녹는과정 실행 ->
simulate 함수
- 두 덩어리 이상으로 분리되었는지 확인 ->
separate 함수
, bfs 함수
main의 반복문
while (true) {
if (melt()) {
answer = 0;
break;
}
simulate();
answer++;
if (separate())
break;
}
System.out.println(answer);
melt
public static boolean melt() {
int cnt = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (arr[i][j] != 0)
cnt++;
}
}
if (cnt == 0)
return true;
else
return false;
}
simulate
- 여기서 계속틀렸던 이유가 배열 한개 안에서 확인하고 변경하고 하다보니 이전 상태를 유지하지 못해서 였다.
- copy배열을 만들어서 이 배열로는 조건 확인만하고, 실제 변경은 기존의 arr에서 해주었다.
public static void simulate() {
int copy[][] = new int[R][C];
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
copy[i][j]=arr[i][j];
}
}
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if(copy[i][j]>0) {
for(int d=0; d<4; d++) {
int nr=i+dr[d];
int nc=j+dc[d];
if(nr>=0 && nc>=0 && nr<R && nc<C) {
if(copy[nr][nc]==0)
arr[i][j]--;
}
}
}
if(arr[i][j]<0)
arr[i][j]=0;
}
}
}
separate, bfs
- 현재 배열에서 빙산이 몇덩어리로 이루어져있는지 확인하는 부분이다.
- 이중포문을 돌면서 빙산(방문하지 않은)을 발견하면 bfs를 이용해 해당 칸과 이어져있는 빙산인 칸들을 전부 방문처리 해주는 방식으로 덩어리 수를 셌다.
public static boolean separate() {
int cnt=0;
visit= new boolean[R][C];
for(int i=0; i<R; i++) {
for(int j=0;j <C; j++) {
if(arr[i][j]>0 && visit[i][j]==false) {
cnt++;
visit[i][j]=true;
bfs(i,j);
}
}
}
if(cnt>=2)
return true;
else
return false;
}
public static void bfs(int r, int c) {
Queue<Point> queue = new ArrayDeque<Point>();
queue.add(new Point(r,c));
while (!queue.isEmpty()) {
Point cur = queue.poll();
for (int d = 0; d < 4; d++) {
int nr = cur.r + dr[d];
int nc = cur.c + dc[d];
if (nr >= 0 && nc >= 0 && nr < R && nc < C && visit[nr][nc] == false && arr[nr][nc]>0) {
visit[nr][nc] = true;
queue.add(new Point(nr, nc));
}
}
}
}
🌱 코드
package week16.boj_2573;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Somyeong {
static class Point {
int r, c;
public Point(int r, int c) {
this.r = r;
this.c = c;
}
}
static int R,C;
static int arr[][];
static int answer;
static int dr[] = { -1, 1, 0, 0 };
static int dc[] = { 0, 0, -1, 1 };
static boolean visit[][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
arr = new int[R][C];
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
while (true) {
if (melt()) {
answer = 0;
break;
}
simulate();
answer++;
if (separate())
break;
}
System.out.println(answer);
}
public static boolean melt() {
int cnt = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (arr[i][j] != 0)
cnt++;
}
}
if (cnt == 0)
return true;
else
return false;
}
public static boolean separate() {
int cnt=0;
visit= new boolean[R][C];
for(int i=0; i<R; i++) {
for(int j=0;j <C; j++) {
if(arr[i][j]>0 && visit[i][j]==false) {
cnt++;
visit[i][j]=true;
bfs(i,j);
}
}
}
if(cnt>=2)
return true;
else
return false;
}
public static void bfs(int r, int c) {
Queue<Point> queue = new ArrayDeque<Point>();
queue.add(new Point(r,c));
while (!queue.isEmpty()) {
Point cur = queue.poll();
for (int d = 0; d < 4; d++) {
int nr = cur.r + dr[d];
int nc = cur.c + dc[d];
if (nr >= 0 && nc >= 0 && nr < R && nc < C && visit[nr][nc] == false && arr[nr][nc]>0) {
visit[nr][nc] = true;
queue.add(new Point(nr, nc));
}
}
}
}
public static void simulate() {
int copy[][] = new int[R][C];
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
copy[i][j]=arr[i][j];
}
}
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if(copy[i][j]>0) {
for(int d=0; d<4; d++) {
int nr=i+dr[d];
int nc=j+dc[d];
if(nr>=0 && nc>=0 && nr<R && nc<C) {
if(copy[nr][nc]==0)
arr[i][j]--;
}
}
}
if(arr[i][j]<0)
arr[i][j]=0;
}
}
}
}