[JAVA]백준_2573_빙산

문제링크

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

2573번: 빙산

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static int map[][];
	static boolean isVisited[][];
	static Queue<Node> q = new LinkedList<>();
	static int dx[] = { 0, 0, -1, 1 };
	static int dy[] = { -1, 1, 0, 0 };
	static int result = 1;

	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());

		map = new int[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());
		}

		while (true) {
			// 빙산 몇 개인지 탐색
			isVisited = new boolean[N][M];

			iceBerg();

			int cnt = 0;
			// 모두 다 0이면 그냥 탈출하고 0
			for (int i = 0; i < N ; i++) {
				for (int j = 0; j < M ; j++) {
					if (map[i][j] == 0)
						cnt++;
				}
			}
			if (cnt == N * M) {
				result = 0;
				break;
			}

			cnt = 0;
			for (int i = 1; i < N - 1; i++) {
				if (cnt == 2)
					break;
				for (int j = 1; j < M - 1; j++) {
					if (cnt == 2)
						break;
					if (map[i][j] != 0 && !isVisited[i][j]) {
						if (cnt == 1) {
							++cnt;
							break;
						}
						q.offer(new Node(i, j));
						bfs();
						cnt++;
					}
				}
			}
			if (cnt == 2)
				break;
			result++;
		}

		System.out.println(result);
	}

	static void iceBerg() {
		Stack<Node> stack = new Stack<>();
		Stack<Node> stack2 = new Stack<>();

		for (int i = 1; i < N - 1; i++) {
			for (int j = 1; j < M - 1; j++)
				if (map[i][j] != 0)
					stack.push(new Node(i, j));
		}

		while (!stack.isEmpty()) {
			Node node = stack.pop();

			int cnt = 0;
			for (int d = 0; d < 4; d++) {
				if (cnt == map[node.x][node.y])
					break; // 현재 빙산의 수와 뺄 숫자가 같으면 포문 벗어나기
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];

				if (nx < 0 || ny < 0 || nx > N || ny > M)
					continue; // 배열 범위 벗어나면 x

				if (map[nx][ny] == 0)
					cnt++;
			}
			
			stack2.push(new Node(node.x,node.y,cnt));
		}

		while (!stack2.isEmpty()) {
			Node node = stack2.pop();
			map[node.x][node.y] = map[node.x][node.y] - node.weight;
		}
	}

	static void bfs() {

		while (!q.isEmpty()) {
			Node node = q.poll();

			for (int d = 0; d < 4; d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];

				if (nx < 0 || ny < 0 || nx > N || ny > M || isVisited[nx][ny])
					continue;

				if (map[nx][ny] != 0) {
					isVisited[nx][ny] = true;
					q.offer(new Node(nx, ny));
				}
			}
		}
	}

	static class Node {
		int x;
		int y;
		int weight;

		public Node(int x, int y, int weight) {
			super();
			this.x = x;
			this.y = y;
			this.weight = weight;
		}

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

 

 

빙산 녹이는 함수
빙산을 하나씩 탐색하면서 녹이면 안되고 탐색하면서 바다의 수?를 구한 뒤에 나중에 한꺼번에 녹여주어야해서
Stack을 사용해서 저장한뒤에 한꺼번에 녹여주었다.

 

bfs로 탐색하면서 한꺼번에 이어지는 지 찾는 함수

 

본문에서는 2개로 나누어질때까지 빙산을 녹이고 -> bfs로 탐색하고 를 반복한다.
처음에는 모두 0이면 끝까지 2로 안나눠지는 것이니까 탐색한다.
후에는 bfs로 탐색하는데 bfs를 한번 들어가고 난 뒤 다시 재진입하는 순간 이미 2개로 확정된다.
따라서 굳이 bfs를 두번 돌리지 않고 2면 탈출하도록 했다.