[백준] 2573 - 빙산 (JAVA)

1. 소요시간 : 30분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 문제 링크 : https://www.acmicpc.net/problem/2573
7. 푼 날짜 : 2023.03.20

1. 사용한 자료구조 & 알고리즘

bfs, 그래프 이론, 구현, 시뮬레이션을 사용했다.

2. 풀이과정

1. 현재좌표의 상, 하 , 좌, 우를 보고 0이 있다면 현재 좌표의 count를 1증가시켜준다. map의 크기만큼 반복
2. 그리고 탐색이 끝나면 빙산의 높이를 해당 좌표의 count 만큼 감소시켜준다. 이때, 0보다 낮아지면 안되므로 0보다 작다면 0으로 설정해준다.
3. 이제 내 bfs로 탐색을 한다. 현재 좌표가 아직 탐색하지 않았고, 1 이상이라면 bfs 메소드로 탐색하고, 탐색한 좌표의 visited는 모두 true로 바꿔준다.
4. 이때 bfs 메소드로 탐색하는 횟수가 2회 이상이라면 얼음 덩어리가 2덩이로 나뉘어진 것이다. 이 때는 break 한다.
5. 이 때 bfs 메소드를 1번도 실행하지 않았다면 얼음이 완전히 녹은 것이고, 이 경우에는 0을 출력해준다. (예외처리)

3. 소스코드

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

public class Main{

	static int map[][];
	static boolean visited[][];
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());

		int N=Integer.parseInt(st.nextToken());
		int 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());
			}
		}
		
		boolean status= true;
		int count = 0;
		 
		while(status) { //status 가 true인동안 반복

			meltIce(); //얼음을 녹이는 메소드
			status = check(); //두 덩이 이상으로 나뉘었는지 체크하는 메소드
			count ++; 
		
			
		}
		
		System.out.println(count);


	}
	public static void meltIce() {
	
		int checkMap[][]=new int[map.length][map[0].length];

		//상, 하, 좌, 우 탐색 후 얼음이면 해당 좌표의 count 증가
		for(int i=0;i<checkMap.length;i++) {
			for(int j=0;j<checkMap[0].length;j++) {
				for(int k=0;k<4;k++) {
					int nextY= i+dy[k];
					int nextX= j+dx[k];
					if(nextY<0||nextX<0||nextY>=map.length||nextX>=map[0].length)
						continue;
					if(map[nextY][nextX]==0)
						checkMap[i][j]++;
				}
			}
		}

		//해당 좌표의 count 만큼 얼음이 녹음
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map[0].length;j++) {
				map[i][j] -= checkMap[i][j];
				if(map[i][j]<0) map[i][j]= 0;
			}
		}


	}
	public static boolean check() {
		
		visited=new boolean [map.length][map[0].length];
		int count = 0;
		
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map[0].length;j++) {
				//해당 좌표가 1 이상이고, 탐색 안했다면 count 증가시키면서 bfs
				if(map[i][j] > 0&& visited[i][j]==false) {
					count ++;

					//2번 이상 탐색한다면 얼음이 2덩이로 나뉜것임
					if(count == 2) 
						return false;
					
					bfs(i,j);
				}
			}
		}
		
		//count가 0이면, 얼음이 완전히 녹은 것임. 0출력
		if(count ==0) {
			System.out.println(0);
			System.exit(0);
		}
		
		return true;
		
	}
	public static void bfs(int y,int x) {
		Queue<Integer[]> queue=new LinkedList<>();
		queue.add(new Integer[] {y,x});
		visited[y][x]=true;
		
		//bfs로 탐색. 나와 이어진 얼음인지 확인
		while(!queue.isEmpty()) {
			Integer temp[]= queue.poll();
			int prevY=temp[0];
			int prevX=temp[1];
			for(int i=0;i<4;i++) {
				int nextY=prevY+dy[i];
				int nextX=prevX+dx[i];
				if(nextY<0||nextX<0||nextY>=map.length||nextX>=map[0].length) 
					continue;
				if(visited[nextY][nextX]||map[nextY][nextX]==0)
					continue;
				
				visited[nextY][nextX]=true;
				queue.add(new Integer[] {nextY,nextX});
			}
			
		}

		
	}
}

4. 결과

만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.
를 읽지 못해서 while 문이 계속 도는 원인으로 시간 초과가 1번 났다.

5. 회고

2주 쉬었더니 사소한 오타가 계속 나가지고 원인 찾는다고 시간을 많이 썼다. i랑 j도 잘못치고, y랑 x도 바꿔서 쳐가지고 중복탐색을 하는 등 시간을 꽤 많이 잡아먹었다.
이 문제 정답률이 25%여서 뭔가 내가 생각하지 못하는 예외가 있을거라고 생각했는데 그런건 없었다. 그냥 다 나처럼 0을 출력하는걸 깜박하고 못봐서 그랬을 것 같다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212