[백준] 2573번 빙산 JAVA (자바) 풀이

문제 2573번 (BFS)

 

 : 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장

   바다 = 0

	2	4	5	3
	3		2	5	2
	7	6	2	4

 

 :  빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 준다

    동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다 (0보다 더 줄어들지 않는다)

   

		2	4	1
	1		1	5
	5	4	1	2

                                    1년 후 빙산

 

 :  빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오

    전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력

 

 

 [입력]

 :  첫 줄에는 행의 개수와 열의 개수를 나타내는 두 정수 N과 M (N과 M은 3 이상 300 이하)

 :  그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수 (0 이상 10 이하)

 :  빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하

    (배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0)

 

 

 [출력]

 :   첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력 (다 녹을 때까지 분리되지 않으면 0을 출력)

 

 

 [과정]

 

 1. bfs를 통해 영역 개수 계산하기

 4방향으로 이동하며 오직 visit함수에 의지하면서 1이상의 지점의 영역을 찾는다

 bfs가 끝날 때마다 영역 count++

 

 2. count로 영역이 나뉘는지 보기

• 끝까지 0이면 0출력
• 두 덩어리 이상 나눠지면 걸린 시간 years 출력
  
  

 3. 1년마다 녹는 영역 계산하는 melting 메서드

1. 현재 좌표를 기준으로 4방향 탐색 했을 때 0의 개수를 찾기
2. 0개 개수만큼 빼기 (가장 최소값은 0으로 고정)
3. 지도 갱신                

 

 

 [코드]

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

public class Main {
    static int N, M, arr[][];
    static int dx[] = {0, 0, 1, -1};
    static int dy[] = {1, -1, 0, 0};
    static boolean visit[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int years = 0;
        while (true) {
            int count = 0;
            visit = new boolean[N][M];

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (arr[i][j] > 0 && !visit[i][j]) {
                        bfs(i, j);
                        count++;
                    }
                }
            }

            if (count == 0) {
                System.out.println(0);
                return;
            }
            if (count > 1) {
                System.out.println(years);
                return;
            }

            melting();
            years++;
        }
    }
    
    static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        visit[x][y] = true;

        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = p[0] + dx[i];
                int ny = p[1] + dy[i];
                if (0 <= nx && nx < N && 0 <= ny && ny < M) {
                    if (!visit[nx][ny] && arr[nx][ny] > 0) {
                        visit[nx][ny] = true;
                        q.add(new int[]{nx, ny});
                    }
                }
            }
        }
    }

    static void melting() {
        int[][] newArr = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] > 0) {
                    int water = 0;
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (0 <= nx && nx < N && 0 <= ny && ny < M && arr[nx][ny] == 0) {
                            water++;
                        }
                    }
                    newArr[i][j] = Math.max(0, arr[i][j] - water);
                }
            }
        }
        arr = newArr;
    }
}

 

 [해설]
     

 :  static int K;
    static char arr[];
    static boolean visit[] = new boolean[10];
    static ArrayList<String> result = new ArrayList<>();
    

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    K = Integer.parseInt(br.readLine());  부등호 개수 입력
    StringTokenizer st = new StringTokenizer(br.readLine());
    arr = new char[K];  부등호 배열
        
 :  for(int i=0; i<K;i++){
            arr[i]=st.nextToken().charAt(0);  문자형으로 입력 받기
            
    }
        
 :  for(int i=0; i<10; i++){  초기 시작지점
            visit[i] = true;  방문처리
            dfs(i,0,i+"");  초기시작지점, count, 누적 문자열
            visit[i] = false;  초기시작지점 변경하려면 방문 취소
    }
        
 :  System.out.println(result.get(result.size()-1));  최대값
    System.out.println(result.get(0));  최소값
    
    
 :  static void dfs(int now, int count, String number){
        if(count==K){  종료조건) count가 K개면 숫자 다 뽑음
            result.add(number);  지금까지 누적 문자들 result에 추가하기
            return;
        }
        
        for(int next=0; next<10; next++){  다음지점 구하기
            if(!visit[next]){  방문전이라면
                if((arr[count]=='<'&&now<next)||(arr[count]=='>'&& now>next)){  조건 충족하면
                    visit[next]=true;  방문처리
                    dfs(next,count+1,number+next);  다음 숫자를 기준으로 다시 dfs
                    visit[next]=false;  만족하는게 없을 경우는 방문처리 취소하고 다른 숫자로 재시작
                }
            }
        }
   }


  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

https://www.acmicpc.net/problem/2573

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *