백준 5212 - 지구 온난화 ( JAVA )

출처 - 백준 알고리즘

5212번: 지구 온난화

---

[ 알고리즘 ] 

( 단순 구현 )

: 사방탐색을 통해, 가라앉을 섬을 체크해준뒤, 남아있는 섬의 행 최소/최대 값, 열 최소/최대 값을 구하여 해당 범위만 출력

• map 의 값을 입력받으며, 섬 'X' 인 부분은 큐에 삽입 
• 큐가 빌 때까지, 사방 탐색을 하며 3~4면이 바다인 부분을 '-' 로 변경 ( 50 년 후에 사라지는 섬 )  
• 가라앉은 섬도 바다로 변경하며 ('-'→'.') , 남아있는 섬의 행/열 범위 구하기 
• 해당 행 / 열 내의 범위만 출력 

 

 

 + 신경써야 할 부분 

1. 해당 map 의 범위가 벗어났을 경우, 모두 바다로 간주 ( 문제에 적혀있지만, 나는 놓쳤었던 부분 .. ) 

2. map 입력을 모두 다 받은 후에 탐색하기 : 아직 입력받지 못한 부분은 null 값이라 바다인지 섬인지 탐색이 안됨 !   

for(int i=0; i<r; i++) {
	String line = br.readLine();
	for(int j=0; j<c; j++) {
	map[i][j] = line.charAt(j); 
	// 만약 섬이라면, 
	if(map[i][j]=='X') // 사방 탐색하며 바다인지 섬인지 체크 
	}
}

▲ 위와 같은 방법으로 if 문에서 사방 탐색을 구현하게 되면, 

◀ 예를 들어,  map[1][1] == 'X' 이고 3면이 바다이기 때문에 가라앉아야 한다. 

하지만 입력받으면서 탐색을 하게 되면, 아직 입력받지 않은 부분이 null('\u0000') 값으로 읽어진다. 

map[0][1] : 바다 / map[1][0] : 바다 / map[1][2] : null / map[2][1] : null ( char[] 의 default 값 ) 

→ 바다가 2면 > 가라앉지 않음 

 

 

3. 가라앉을 부분은 바로 바다('.') 로 바꾸지 않고, 큐 탐색 끝난 이후에 바꾸기 

while(!que.isEmpty()) {
	Point p = que.poll();
	int x = p.x;
	int y = p.y;
			
	int cnt = 0; 
	// 사방에 섬이 몇개 있는지 탐색 
	for(int d=0; d<4; d++) {
		int nx = x+dx[d];
		int ny = y+dy[d];			
		if(nx<0 || ny <0 || nx>=r || ny>=c || map[nx][ny]=='.') cnt++; 
	}
	// 인접한 3-4면이 바다라면 잠겨버림 
	if (cnt>=3) map[x][y] = '.'; 
}

▲ 위와 같은 방법으로 50 년 후에 가라앉을 섬을 바다 ('.') 로 바꾸게 되면, 

◀ 예를 들어,  map[1][1] == 'X' 이고 3면이 바다이기 때문에 map[1][1] = '.' 가 된다. 

이후 map[2][1] 은 원래 2면이 바다로 가라앉으면 안되는데, 이전 탐색에서 map[1][1]을 바다('.')로 변경해두었으므로 3면이 바다가 되어 가라앉게 된다. 

그래서 가라앉을 섬은 다른 문자로 표기해두고 while 문 탐색이 모두 끝난 이후에 바다로 바꿔주었다. 

 

---

[ 코드 ] 

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

public class BaekJoon_Solution_5212 {
	static int dx[] = {-1,1,0,0}; //상,하,좌,우
	static int dy[] = {0,0,-1,1};
	
	static class Point{
		int x ; 
		int y ;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static void main(String args[]) throws Exception{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ; 
		Queue<Point> que= new LinkedList<>();
		
		String s= br.readLine();
		st= new StringTokenizer(s, " ");		
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		char[][] map = new char[r][c];
		
		// 섬인 부분의 행 최소/최대 값, 열 최소/최대 값
		int minr = r-1; 
		int maxr = 0; 
		int minc = c-1;
		int maxc = 0; 
		
		for(int i=0; i<r; i++) {
			String line = br.readLine();
			for(int j=0; j<c; j++) {
				map[i][j] = line.charAt(j); 
				// 만약 섬이라면, 
				if(map[i][j]=='X') que.add(new Point(i,j));
			}
		}
		
		while(!que.isEmpty()) {
			Point p = que.poll();
			int x = p.x;
			int y = p.y;
			
			int cnt = 0; 
			// 사방에 섬이 몇개 있는지 탐색 
			for(int d=0; d<4; d++) {
				int nx = x+dx[d];
				int ny = y+dy[d];
				
                //인접한 면이 바다라면, cnt ++ 
				if(nx<0 || ny <0 || nx>=r || ny>=c || map[nx][ny]=='.') cnt++; 

			}
			// 인접한 3-4면이 바다라면 잠겨버림 
			if (cnt>=3) map[x][y] = '-'; 
			
		}
	
		// 50년 뒤 , 
		for(int i=0; i<r; i++) {
			for(int j=0; j<c; j++) {
				if(map[i][j] =='-') map[i][j]='.'; 
				
				if(map[i][j]=='X') {
					minr= Math.min(minr, i); 
					maxr= Math.max(maxr, i); 
					minc= Math.min(minc, j);
					maxc= Math.max(maxc, j); 
				}
			}
		}
        
        //섬이 존재하는 최소 직사각형 출력 
		for(int i=minr; i<=maxr; i++) {
			for(int j=minc; j<=maxc; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}	
	}
}