[백준/java] 2573. 빙산

somyeong·2022년 12월 15일
0

코테 스터디

목록 보기
44/52

문제 링크 - https://www.acmicpc.net/problem/2573

🌱 문제


🌱 풀이

  • 문제에서 요구하는 그대로 구현하면 되는 문제였다.
  • 함수 하나 당 하나의 기능을 하도록 나눴더니 함수가 좀 많아졌다.
  • 시뮬레이션하는 반복문 안에서 아래과정 반복
  1. 두 덩어리 이상으로 분리되기 전에 다 녹았는지 확인 -> melt 함수
  2. 빙산 녹는과정 실행 -> simulate 함수
  3. 두 덩어리 이상으로 분리되었는지 확인 -> separate 함수, bfs 함수

  • 주석과 함께 각 함수부분 살펴보기

main의 반복문

while (true) {
			if (melt()) { // 두 덩어리 이상으로 분리되기 전에 다 녹았으면 0 출력하고 종료 
				answer = 0;
				break;
			}
			
			simulate();
			answer++;
			
			if (separate()) //두 덩어리 이상으로 분리되면 반복 종료하고 정답 출력 
				break;
		}
		System.out.println(answer);

melt

public static boolean melt() { // 다 녹았으면 true, 아니면 false
		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() { // 사방에 0이 저장된 칸의 갯수만큼 줄어듦 
		int copy[][] = new int[R][C]; 
		// 빙산배열을 새로운 배열에 복사해둔 후, 복사해둔 배열의 사방을 확인하면서 기존 빙산배열의 수를 줄여주어야 한다.
		// 이전 simulate한 결과를 기준으로 변경해야하는데, 기존배열 하나로 체크하면서 수 줄여주면 이전 상태가 유지되지않아서 잘못된 결과가 나올 수 있다. 
		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) // 음수라면 0으로 변경 
					arr[i][j]=0;
			}
		}
	}

separate, bfs

  • 현재 배열에서 빙산이 몇덩어리로 이루어져있는지 확인하는 부분이다.
  • 이중포문을 돌면서 빙산(방문하지 않은)을 발견하면 bfs를 이용해 해당 칸과 이어져있는 빙산인 칸들을 전부 방문처리 해주는 방식으로 덩어리 수를 셌다.
public static boolean separate() { // 두덩어리 이상으로 분리되면 true, 아니면 false
		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) { //같은 덩어리인지 확인하는 bfs 
		
		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) {// 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;

//2573. 빙산 
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()) { // 두 덩어리 이상으로 분리되기 전에 다 녹았으면 0 출력하고 종료 
				answer = 0;
				break;
			}
			
			simulate();
			answer++;
			
			if (separate()) //두 덩어리 이상으로 분리되면 반복 종료하고 정답 출력 
				break;
		}
		System.out.println(answer);
	}

	public static boolean melt() { // 다 녹았으면 true, 아니면 false
		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() { // 두덩어리 이상으로 분리되면 true, 아니면 false
		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) { //같은 덩어리인지 확인하는 bfs 
		
		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) {// arr[nr][nc]>0 체크 주의 
					visit[nr][nc] = true;
					queue.add(new Point(nr, nc));
				}
			}

		}
	}
	public static void simulate() { // 사방에 0이 저장된 칸의 갯수만큼 줄어듦 
		int copy[][] = new int[R][C]; 
		// 빙산배열을 새로운 배열에 복사해둔 후, 복사해둔 배열의 사방을 확인하면서 기존 빙산배열의 수를 줄여주어야 한다.
		// 이전 simulate한 결과를 기준으로 변경해야하는데, 기존배열 하나로 체크하면서 수 줄여주면 이전 상태가 유지되지않아서 잘못된 결과가 나올 수 있다. 
		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) // 음수라면 0으로 변경 
					arr[i][j]=0;
			}
		}
	}

}
profile
공부한 내용 잊어버리지 않게 기록하는 공간!

0개의 댓글