Inor

[백준] 2573번 빙산 본문

Algorithm/백준

[백준] 2573번 빙산

Inor 2018. 1. 12. 16:58

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


 rowN x colN 크기의 행렬에 빙산과 바다가 표시됩니다. 빙산은 0 이상의 숫자로 바다는 0으로 표시됩니다. 빙산은 바다와 맞닿아 있는 수 많큼 빠르게 줄어들고 빙하가 두조각 이상으로 나뉠때까지 빙하를 녹이는 문제입니다. 문제가 지난번에 풀었던 안전영역과 비슷합니다. 


안전영역 문제 및 풀이 : http://inor.tistory.com/26?category=723636




- 풀이


 먼저 빙하를 방문했습니다. 방문을 위해 DFS를 이용했고 DFS를 이용한 이유는 빙산이 몇조각으로 나뉘어져 있는지 확인하기 위해서였습니다. 방문 함수를 2번 이상 호출하면 빙하가 2조각 이상이라는 말이고 2번 이상 호출 됐을 경우에 탐색을 종료했습니다. DFS 내부에서 stack을 pop하고 이전 빙하로 넘어갔을때 이미 방문한 빙하이면 빙하를 녹이는 연산을 수행하지 않았습니다. 그리고 DFS를 호출하고난 후에 zeroCnt로 0의 갯수를 확인했습니다. zeroCnt는 빙하가 있었던 위치가 모두 0으로 변할 동안 2조각으로 나뉘어졌는지를 확인하기 위한 변수입니다. zeroCnt라는 변수를 선언해서 빙하가 모두 녹았지만 그 전까지 빙하가 두조각으로 나뉘어지지 않았을 경우를 확인했습니다.



- 코드


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class Iceberg {
	BufferedReader br;
	Stack<Point> s;
	int rowN, colN;
	static int icebergCount, year;
	int[][] map, tempMap;
	int[] dRow, dCol;
	boolean[][] check;

	void setValues() {
		String[] temp;
		br = new BufferedReader(new InputStreamReader(System.in));
		s = new Stack<Point>();
		dRow = new int[] { -1, 0, 1, 0 };
		dCol = new int[] { 0, 1, 0, -1 };
		icebergCount = 0;
		year = 0;
		try {
			temp = br.readLine().split(" ");
			rowN = Integer.parseInt(temp[0]);
			colN = Integer.parseInt(temp[1]);
			map = new int[rowN][colN];
			tempMap = new int[rowN][colN];
			check = new boolean[rowN][colN];
			for (int i = 0; i < rowN; i++) {
				temp = br.readLine().split(" ");
				for (int j = 0; j < colN; j++) {
					map[i][j] = Integer.parseInt(temp[j]);
					tempMap[i][j] = map[i][j];
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	void search(int row, int col) {
		icebergCount++;
		s.push(new Point(row, col));
		Point searchPoint;
		int nRow, nCol;
		boolean endPoint = true;

		while (s.isEmpty() == false) {
			searchPoint = s.peek();
			endPoint = true;

			for (int dir = 0; dir < 4; dir++) {
				if (check[searchPoint.pRow][searchPoint.pCol] == true) {
					break;
				}

				nRow = searchPoint.pRow + dRow[dir];
				nCol = searchPoint.pCol + dCol[dir];
				if ((nRow >= 0 && nRow < rowN) && (nCol >= 0 && nCol < colN)) {
					if (map[nRow][nCol] == 0) {
						tempMap[searchPoint.pRow][searchPoint.pCol]--;
						if (tempMap[searchPoint.pRow][searchPoint.pCol] <= 0) {
							break;
						}
					}
				}
			}

			check[searchPoint.pRow][searchPoint.pCol] = true;
			for (int dir = 0; dir < 4; dir++) {
				nRow = searchPoint.pRow + dRow[dir];
				nCol = searchPoint.pCol + dCol[dir];
				if ((nRow >= 0 && nRow < rowN) && (nCol >= 0 && nCol < colN)) {
					if (check[nRow][nCol] == false && map[nRow][nCol] > 0) {
						endPoint = false;
						s.push(new Point(nRow, nCol));
						break;
					}
				}
			}

			if (endPoint) {
				s.pop();
			}
		}
	}

	public int solve() {
		setValues();
		boolean elseIceberg = false;
		int zeroCnt = 0;

		while (icebergCount == 0) {
			for (int i = 1; i < rowN - 1; i++) {
				for (int j = 1; j < colN - 1; j++) {
					if (check[i][j] == false && map[i][j] > 0) {
						search(i, j);
					}
					if (icebergCount >= 2) {
						return year;
					}
					if(tempMap[i][j] == 0){
						zeroCnt++;
					}
				}
			}
			for (int k = 0; k < rowN; k++) {
				map[k] = Arrays.copyOf(tempMap[k], tempMap[k].length);
				Arrays.fill(check[k], false);
			}

			year++;
			icebergCount = 0;
			if(zeroCnt == (rowN - 2) * (colN - 2)){
				return 0;
			}
			zeroCnt = 0;
		}
		return 0;
	}

	public static void main(String[] args) {
		Iceberg m = new Iceberg();

		System.out.println(m.solve());
	}

	class Point {
		public int pRow, pCol;

		public Point(int pRow, int pCol) {
			this.pRow = pRow;
			this.pCol = pCol;
		}
	}

}

'Algorithm > 백준' 카테고리의 다른 글

[백준] 12761번 돌다리  (0) 2018.01.31
[백준] 1992번 쿼드트리  (0) 2018.01.28
[백준] 1963번 킹  (0) 2018.01.11
[백준] 1932번 숫자 삼각형  (0) 2018.01.10
[백준] 14890번 경사로  (0) 2018.01.03
Comments