[2573,Java] 백준 - 빙산 ( BFS )

https://www.acmicpc.net/status?user_id=smyang0220&problem_id=2573&from_mine=1

채점 현황

11월 04일 토요일 황금같은 주말에 생각보다 많은 시간을 투자한 문제다...

1시간 30분정도 푼 것 같다.

 

틀렸던 원인

1. 빙산 수를 감소시키는 것을 같은 배열안에서 진행을 해서 다른 빙산의 수 감소에 영향을 줌

=> 복사배열을 준비

 

2. 한번에 다 녹았을 때 0 출력

문제를 똑바로 읽지 않아서 해맸던 것 같다.

앞으로 문제를 정독하자..

 

 

이 문제는 BFS를 사용해서 해결해야하는 문제다.

처음 배열을 입력 받을 때 0보다 큰 값들을 확인해 빙산 수를 확인하고

제거 하는 함수에서 제거된 빙산이 0보다 작아지면 전체 빙산수를 감소시키는 방식으로 작성했다.

 

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

public class Main {
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int height;
	static int width;
	static int[][] map; // 빙산 배열
	static int[][] map2; // 제가된 빙산을 옮겨닮을 배열
	static int ice;
	static boolean check;
	
	static class Point{
		int x,y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		height = Integer.parseInt(st.nextToken());
		width = Integer.parseInt(st.nextToken());

		ice = 0; // 빙산의 총 갯수
		map = new int[height][width];
		map2 = new int[height][width];
		for (int i = 0; i < height; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < width; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] > 0) {
					ice++; // 빙산갯수 증가
				}
				
			}
		} // 입력완료
		int result = 0;
		check = false; // 한번에 녹았을 경우를 대비
		while(true) {
			// 빙산 이어져있는지 검사
			if(!BFS(ice)) { // 제대로 다 이어져있지 않다면
				break;
			}
			
			// 제대로 이어져있다면 1년 지나니까 결과값 1 증가
			result++;
			//System.out.println(result);
			year(); // 감소했으니 배열 옮겨 담아야함
			
			
			for(int i = 0; i < height; i++) {
				for(int j = 0; j<width; j++) {
					map[i][j] = map2[i][j];
				}
			}// 옮겨담기 완료
			
			
		}
		if(check == false) { // 한번에 녹은게 아니라면			
			System.out.println(result);
		}else {
		//	System.out.println("check");
			System.out.println(0);
		}
		
		
		
		
		
	}// main
	
	// 빙산 제거 함수
	static public void year() {
		for(int i = 0; i<height; i++) {
			for(int j = 0; j< width; j++) {
				if(map[i][j] >0 ) {
					map2[i][j] = map[i][j] -delete(i, j);
					if(map2[i][j] <= 0) {
						ice--; // 연산 후 0보다 작으면 빙산 수 감소
					}
				}
			}
		}
	}
	
	
	static public int delete(int x, int y) {
		int result = 0;
		for (int i = 0; i < 4; i++) {
			int X = x + dx[i];
			int Y = y + dy[i];
			if (X >= 0 && X < height && Y >= 0 && Y < width && map[X][Y] <= 0) {
				result++;
			}
		}
		return result;
	}

	
	 // 탐색 함수
	static public boolean BFS(int cnt) { // 매개변수는 남아있는 빙산 갯수
		int idxx = -1;
		int idxy = -1;
		for(int i = 0; i<height; i++) {
			for(int j= 0; j < width; j++ ) {
				if(map[i][j] > 0) {
					idxx = i;
					idxy = j;
				}
			}
		}// 시작할 점을 못찾았다면 한번에 다 녹은 것임
		if(idxx == -1) {
			check = true;
			return false;
		}
		
		int count = 0;
		boolean[][] flag = new boolean[height][width];
		Queue<Point> points = new LinkedList<>();
		points.add(new Point(idxx, idxy));
		while (!points.isEmpty()) {
			Point P = points.poll();
			count++;
			int x = P.x;
			int y = P.y;

			//System.out.println("x = " + x + " y =  "+y);
			for (int i = 0; i < 4; i++) {
				int X = x + dx[i];
				int Y = y + dy[i];
				if (X >= 0 && X < height && Y >= 0 && Y < width && map[X][Y] > 0 && flag[X][Y] == false) {
					flag[X][Y] = true;
					points.add(new Point(X, Y));
				//	System.out.println("add queue X = " + X + "  add queue Y = " + Y);
				}
			}

		} // BFS 종료
		//System.out.println("count = " + count +" Cnt = " + cnt);
		
		if(count > cnt) {
			//System.out.println("true");
			return true;
		}else {
		//	System.out.println("false");
			return false;
		}
		
		
		
		
	}
	
	
}

 

 

내 황금같은 주말. 알찼다.

주인장은 이만 이제 플러터 초기설정하러 가보겠다.