[Java] BOJ2573, 백준 - 빙산

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

2573번: 빙산

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256MB	39897	11238	7356	25.687%

문제

백준 사이트를 참고해주세요

 

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

 

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

 

<풀이>

*시간복잡도

초기 배열 검사: n*m <= 90000

빙산인 칸 <= 10000

빙산인 칸의 사방탐색 : 40000

각 칸에 들어가는 값은 10이하이니 최대 10번까지만 반복함

40000*10 = 400000+90000 = 약 50만

 

빙산이 처음으로 분리되는 해를 찾아야 한다!!

 >  boolean 변수를 선언하고 while문으로 반복하자

 

(1) 분리되는지 찾기

총 빙산의 수를 tot변수에 저장하고, 한 지점에서부터 탐색을 진행하며 그 지점으로부터 진행된 bfs의 크기가 tot와 일치하지 않는다? > 그러면 다른 덩어리의 빙산이 더 있다는 의미임

int curr = 0; // 현재 빙산의 크기
int next = tot; // 다음 빙산의 총 크기

// 다 녹은 칸이 생겼다면 내년에는 총 빙산의 수가 하나 줄어들겠지?
if(map[y][x] == 0)
	next--;

// 만약 현재 빙산수와 총 빙산수가 다르다면 다른 빙산 덩어리가 또 있다는 의미: 종료
if(tot != curr){
	System.out.println(year);
    return;
}

// 빙산이 한꺼번에 다 녹았을 경우 : 트리거 변경
if(tot == 0){
	isMelt = true;
}

 

(2) 빙산이 얼마나 녹는지 탐색

사방탐색으로 인접한 0의 갯수를 비교

하지만 원래 빙산이었던 칸이 올해 녹으면서 0으로 변했을 수도 있음!

이러한 경우에는 카운팅하면 안되기때문에, 따로 boolean visited[]배열으로 체크해주었다.

visited[y][x] = true;
curr++;

// 4방향 탐색
for (int k = 0; k < 4; k++) {
	int ny = y + move[k][0];
	int nx = x + move[k][1];

	if (ny >= n || nx >= m || ny < 0 || nx < 0) // 인덱스 유효성 검사
		continue;

		if (visited[ny][nx] || map[ny][nx] >= 1) {
			// 빙산인 경우 : 큐에 넣기
			q.add(new Point(ny, nx));
		} else {
			// 바다인 경우: 현재높이 감소
			if (map[y][x] >= 1)
				map[y][x]--;
		}
} // end 4방탐색

 

 

 

<전체 소스코드>

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

// 백준 2573
public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 행 수
		int m = Integer.parseInt(st.nextToken()); // 열 수

		int[][] move = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

		int[][] map = new int[n][m];
		int year = 0; // 바퀴 수 저장
		int tot = 0;

		// 입력부
		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());
				if (map[i][j] != 0)
					tot++;
			}
		} // end Input

		boolean isMelt = false;
		while (!isMelt) {
			boolean[][] visited = new boolean[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (map[i][j] == 0 || visited[i][j])
						continue;

					int curr = 0;
					int next = tot;
					Queue<Point> q = new LinkedList<>();
					q.add(new Point(i, j));
					while (!q.isEmpty()) {
						Point p = q.poll();
						int x = p.x;
						int y = p.y;

						if (visited[y][x])
							continue;

						visited[y][x] = true;
						curr++;

						// 4방향 탐색
						for (int k = 0; k < 4; k++) {
							int ny = y + move[k][0];
							int nx = x + move[k][1];

							if (ny >= n || nx >= m || ny < 0 || nx < 0) // 인덱스 유효성 검사
								continue;

							if (visited[ny][nx] || map[ny][nx] >= 1) {
								// 빙산인 경우 : 큐에 넣기
								q.add(new Point(ny, nx));
							} else {
								// 바다인 경우: 현재높이 감소
								if (map[y][x] >= 1)
									map[y][x]--;
							}
						} // end 4방탐색

						if (map[y][x] == 0)
							next--;
					} // end BFS

					if (tot != curr) {
						System.out.println(year);
						return;
					}
					year++;

					tot = next;
					if (tot == 0) {
						// 다 녹음 > 분리영역 찾을 수 없음: while문을 탈출하여 0 출력
						isMelt = true;
					}
				}
			} // 2중for문
		} // isSeperated
		System.out.println("0"); // 한꺼번에 녹을 경우 0 출력
	} // end main
} // end class

class Point {
	int x, y;

	Point(int y, int x) {
		this.x = x;
		this.y = y;
	}
}

 

 

함수좀 쓸걸 그랬다. 코드 넘 복잡함