[Baekjoon] 백준 2573 빙산 (G4^ / BFS) - Java

링크

https://www.acmicpc.net/problem/2573

2573번: 빙산

 

 

 

 

문제 해석

빙산을 2차원 배열에 표시

빙산의 부분별 높이 정보는 배열 각 칸에 저장

바다에 해당하는 칸은 0이 저장

바닷물에 많이 접해있으면 빨리 줄어듬

4방향 중 바다에 접한 면만큼 줄어듦

 

입력

첫 번째 줄 : N M

  행 : N

  열 : M

나머지 줄 : 행만큼 반복적으로 입력

 

출력

한 덩어리의 빙산이 주어질 때 빙산이 두 덩어리 이상으로 분리되는 최초 시간

다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 0 출력

 

 

 

 

풀이 & 코드 해석

살짝 치즈 문제가 생각나게 하는 문제였습니다.

https://angelplayer.tistory.com/485

[Baekjoon] 백준 2638 치즈 (G3 / BFS) - Java

 

 

치즈와 다른 점은 빙하가 녹아서 두 개로 쪼개지는 시점을 정답으로 하기 때문에, 시간이 흐를 때마다 쪼개졌는지 체크하는 bfs를 한 번 더 사용하였습니다.

 

 

 

 

코드

package test;

import java.io.*;
import java.util.*;

public class 빙산 {
	
	static int[][] map;
	static boolean[][] island;
	static boolean[][] v;
	static int answer = 0;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 첫 번째 줄
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		island = new boolean[N][M];
		v = new boolean[N][M];
			
		// 두 번째 줄
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		
		for(int now = 0; ; now++) {
			
			// 두 덩어리로 쪼개졌는지 확인
			int islandCheck = 0;
			island = new boolean[N][M];
			v = new boolean[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (map[i][j] < 0) {
						map[i][j] = 0;
					}
					if(map[i][j] > 0 && island[i][j] == false) {
						bfs(i, j);
						islandCheck += 1;
					}
				}
			}
//			print();
			
			if (islandCheck > 1) {

				answer = now;
				break;
			} else if (islandCheck == 0) {
				answer = 0;
				break;
			}
			
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(map[i][j] > 0 && v[i][j] == false) {
						bfs2(i, j);
					}
				}
			}
		}
		
		System.out.println(answer);
		
	}
	
	static void print() {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
		
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				System.out.print(island[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	static int[] nr = {-1, 0, 1, 0};
	static int[] nc = {0, 1, 0, -1};
	
	static class Point {
		int r;
		int c;
		
		Point (int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	static void bfs(int i, int j) {
		Queue<Point> q = new LinkedList<>();
		q.offer(new Point(i, j));
		island[i][j] = true;
		
		while(!q.isEmpty()) {
			Point p = q.poll();
			for (int d = 0; d < nr.length; d++) {
				int dr = p.r + nr[d];
				int dc = p.c + nc[d];
				
				if (dr >= 0 && dr < map.length && dc >= 0 && dc < map[0].length 
						&& island[dr][dc] == false && map[dr][dc] > 0) {
					island[dr][dc] = true;
					q.offer(new Point(dr, dc));
				}
			}
		}
	}
	
	static void bfs2(int i, int j) {
		Queue<Point> q = new LinkedList<>();
		q.offer(new Point(i, j));
		v[i][j] = true;
		
		while(!q.isEmpty()) {
			Point p = q.poll();
			for (int d = 0; d < nr.length; d++) {
				int dr = p.r + nr[d];
				int dc = p.c + nc[d];
				
				if (dr >= 0 && dr < map.length && dc >= 0 && dc < map[0].length) {
					// 인접한 곳이 빙산이 아니라면
					if (island[dr][dc] == false) {
						map[p.r][p.c] -= 1;
					} else if (v[dr][dc] == false) {						
						q.offer(new Point(dr, dc));
						v[dr][dc] = true;
					}
				}
			}
		}
	}

}

 

 

 

 

발생한 문제 & 해결 방안

생각보다 시간이 오래걸렸다.

 

처음 bfs에서 Queue에 offer할 때 island[i][j] = true; v[i][j] = true;를 하지 않아서 해당 위치가 중복 연산 되는 경우가 있었다.

조건을 잘 지정하자.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java