[백준] 알고리즘 분류(구현,JAVA)2573번, 빙산

문제 링크

2573번: 빙산

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 1년마다 빙산은 주위(상하좌우)의 바다('0')인 개수만큼 높이가 감소합니다.

2. 배열의 첫, 마지막 행과 열에는 항상 0으로 채워집니다.

3. 빙산이 2개의 영역으로 나눠지는 최초 시간을 결과로 출력합니다.

4. 빙산이 다 녹을 때까지 영역 2개 이상으로 나눠지지 않으면 0을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 1년마다 빙산이 녹는 시뮬레이션을 진행합니다.

 

3. 시뮬레이션에 따른 결과를 출력합니다.

 

 

시뮬레이션.

 

저는 Queue를 이용해서 현재 빙산의 위치를 저장하였습니다.

 

진행 과정

 

1) 모든 빙산 위치 기준 상하좌우 바다의 개수 탐색

 

2) 바다의 개수만큼 모든 빙산의 높이 감소

 

3) BFS탐색으로 영역 개수 확인

 

4) 영역의 개수에 따라 진행

 

4-1) 영역의 개수가 2개 이상일 때 시뮬레이션 종료

 

4-2) 영역의 개수가 1개 이하일 때 1)번 다시 진행

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 5
K : 7

 

빙산

 

0	0	0	0	0	0	0
0	2	4	5	3	0	0
0	3	0	2	5	2	0
0	7	9	2	4	0	0
0	0	0	0	0	0	0

 

2. 1년마다 빙산이 녹는 시뮬레이션을 진행합니다.

 

시뮬레이션 진행!

 

1) 모든 빙산 바다의 개수 확인

 

0	0	0	0	0	0	0
0	2(2)	4(2)	5(1)	3(2)	0	0
0	3(2)	0	2(1)	5(0)	2(2)	0
0	7(2)	9(2)	2(1)	4(2)	0	0
0	0	0	0	0	0	0

 

2) 바다의 개수만큼 모든 빙산의 높이 감소

 

0	0	0	0	0	0	0
0	0	2	4	1	0	0
0	1	0	1	5	0	0
0	5	7	1	2	0	0
0	0	0	0	0	0	0

 

3) BFS탐색으로 영역 개수 확인

 

0	0	0	0	0	0	0
0	0	2	4	1	0	0
0	1	0	1	5	0	0
0	5	7	1	2	0	0
0	0	0	0	0	0	0

영역 개수 : 1개

 

4-2) 영역의 개수가 1개 이하일 때 1)번 다시 진행

1) 모든 빙산 바다의 개수 확인

0	0	0	0	0	0	0
0	0	2(3)	4(1)	1(2)	0	0
0	1(4)	0	1(1)	5(1)	0	0
0	5(2)	7(2)	1(1)	2(2)	0	0
0	0	0	0	0	0	0

 

2) 바다의 개수만큼 모든 빙산의 높이 감소

 

0	0	0	0	0	0	0
0	0	0	3	0	0	0
0	0	0	0	4	0	0
0	3	5	0	0	0	0
0	0	0	0	0	0	0

 

3) BFS탐색으로 영역 개수 확인

 

0	0	0	0	0	0	0
0	0	0	3	0	0	0
0	0	0	0	4	0	0
0	3	5	0	0	0	0
0	0	0	0	0	0	0

영역 개수 : 3개

 

4-1) 영역의 개수가 2개 이상일 때 시뮬레이션 종료

 

3. 시뮬레이션에 따른 결과를 출력합니다.

 

영역 2개 이상이 생겼으므로 지나간 년도를 결과로 출력합니다.

 

지나간 년도 : 2년

 

2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 빙산에 대한 정보를 띄어쓰기 기준 나누었습니다.
• 빙산의 위치를 따로 Queue에 저장하였습니다.
• 빙산이 녹는 시뮬레이션을 순서에 맞게 진행합니다.
• 시뮬레이션에 따른 결과를 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• mapCheck함수는 BFS탐색으로 빙산의 영역을 탐색합니다.

 

결과코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
    //빙산 위치 관련 클래스
    static class iceberg{
        //x : 열, y : 행, count : 주변 바다 개수
        int x, y, count = 0;
        public iceberg(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y변경값
    //빙산 위치 저장 Queue
    static Queue<iceberg> icebergs = new LinkedList<>();
    static int[][] map;	//바다 및 빙산 높이 저장된 배열
    static boolean[][] visited;	//빙산 방문 확인 배열
    static int N,M;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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++){
                int n = Integer.parseInt(st.nextToken());
                if(n != 0)
                    icebergs.add(new iceberg(j, i));
                map[i][j] = n;
            }
        }
        int answer = 0;
        //시뮬레이션 진행!
        while(true){
            //빙산이 모두 녹았을 때
            if(icebergs.isEmpty()){
                answer = 0;
                break;
            }
            answer++;	// 1년 추가!
            int size = icebergs.size();
            //1) 모든 빙산 바다의 개수 확인
            for(iceberg cur : icebergs){
                cur.count = 0;
                for(int j=0;j<4;j++){
                    int tempX = cur.x + dx[j];
                    int tempY = cur.y + dy[j];
                    if(map[tempY][tempX] == 0)
                        cur.count++;
                }
            }
            //2) 바다의 개수만큼 모든 빙산의 높이 감소
            for(int i=0;i<size;i++){
                iceberg cur = icebergs.poll();
                map[cur.y][cur.x] = Math.max(0, map[cur.y][cur.x] - cur.count);
                if(map[cur.y][cur.x] != 0)
                    icebergs.add(cur);
            }
            int count = 0;
            visited = new boolean[N][M];
            //3) BFS탐색으로 영역 개수 확인
            for(iceberg cur : icebergs){
                if(!visited[cur.y][cur.x]){
                    mapCheck(cur.y, cur.x);
                    count++;
                }
            }
            //4-1) 영역의 개수가 2개 이상일 때 시뮬레이션 종료
            if(count >= 2)
                break;
        }
        bw.write(answer + "");	//시뮬레이션에 따른 결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색으로 빙산의 영역 확인하는 함수
    static void mapCheck(int y, int x){
        Queue<iceberg> queue = new LinkedList<>();
        visited[y][x] = true;	//기준 빙산 방문 확인
        queue.add(new iceberg(x, y));	//기준 빙산 저장
        //BFS탐색 진행
        while(!queue.isEmpty()){
            iceberg cur = queue.poll();
            //상하좌우 탐색
            for(int i=0;i<4;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                //방문하지 않았던 빙산일 경우
                if(map[tempY][tempX] != 0 && !visited[tempY][tempX]){
                    visited[tempY][tempX] = true;
                    queue.add(new iceberg(tempX, tempY));
                }
            }
        }
    }
}