백준 2573 빙산(DFS+BFS)

알고리즘

백준 2573 빙산(DFS+BFS)

킨글 2022. 8. 31. 21:38

문제 접근 방법

1. mapCountDFS를 통해 빙산이 두 덩어리 이상으로 되어 있는지 확인을 진행한다.

2. globalWarmingBFS를 통해 빙산을 녹여주는 작업을 진행한다.

헷갈렸던 점

- 빙산이 녹으면서 한번에 모두 0이 되어 덩어리가 0이 되는 경우를 잘못 처리해줬었다.

그래서 녹으면서 한번에 모두 0이 되면 result = 0; 으로 다시 초기화를 진행해주었다.

int result = 0;
while(true){
    int mapCount = countMapDFS();
    if(mapCount == 0){ // 모두 녹아 있을 때에 처리
        result = 0;
        break;
    }
    ...
    ...
}

- 6%에서 계속 틀렸습니다.가 떠서 질문 게시판에 있는 반례를 모두 적용해보았으나, 정상 작동하였다.

그래서 구조를 다시 천천히 보던 중 visited[nx][ny] = true; 처리가 어색한 부분을 발견하였다.

다음 map[nx][ny] 경로가 0일 때에 visited 처리를 해주면, 다른 경로에서 해당 map[nx][ny] == 0인 경로를 탐색하지 못하게 되기 때문이었다.

그래서 0인 곳은 방문 처리를 하지 않기 위해 if(map[nx][ny] == 0) continue; 부분 밑으로 내려주어 해결하였다.

<기존>

if(map[nx][ny] == 0 && map[p.x][p.y] > 0){
    map[p.x][p.y] -= 1;
    continue;
}
visited[nx][ny] = true;
if(map[nx][ny] == 0) continue;

q.add(new IceBerg(nx, ny));

<변경>

if(map[nx][ny] == 0 && map[p.x][p.y] > 0){
                    map[p.x][p.y] -= 1;
                    continue;
                }
if(map[nx][ny] == 0) continue;

visited[nx][ny] = true;
q.add(new IceBerg(nx, ny));

소스 코드

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 {
    public static void main(String[] args) throws IOException {
        solution();
    }
    static int N;
    static int M;
    static int map[][];
    static boolean visited[][];
    static int[] dx;
    static int[] dy;
    static void solution() 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());
        map = new int[N][M];
        visited = new boolean[N][M];
        dx = new int[]{-1, 1, 0, 0};
        dy = new int[]{0, 0, -1, 1};

        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());
            }
        }

        int result = 0;
        while(true){
            int mapCount = countMapDFS();
            if(mapCount == 0){ // 모두 녹아 있을 때에 처리
                result = 0;
                break;
            }

            if(mapCount > 1){ // 지역이 2개 이상이면 탈출
                break;
            }
            globalWarmingBFS(); // 녹이기
            result += 1;
        }
        System.out.println(result);
    }
    static class IceBerg{
        int x;
        int y;

        public IceBerg(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static void dfs(int x, int y){
        visited[x][y] = true;
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if(visited[nx][ny] || map[nx][ny] == 0) continue;

            dfs(nx, ny);
        }
    }
    static int countMapDFS(){
        int cnt = 0;
        visited = new boolean[N][M];
        for(int i=0; i<N; i++){
            for (int j = 0; j < M; j++) {
                if(!visited[i][j] && map[i][j] > 0){
                    dfs(i, j);
                    cnt++;
                    if(cnt > 1) return cnt;
                }
            }
        }
        return cnt;
    }
    static void bfs(int x, int y){
        Queue<IceBerg> q = new LinkedList<>();
        q.add(new IceBerg(x, y));
        visited[x][y] = true;

        while(!q.isEmpty()) {
            IceBerg p = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if(visited[nx][ny]) continue;
                if(map[nx][ny] == 0 && map[p.x][p.y] > 0){
                    map[p.x][p.y] -= 1;
                    continue;
                }
                if(map[nx][ny] == 0) continue;
                
                visited[nx][ny] = true;
                q.add(new IceBerg(nx, ny));
            }
        }
    }
    static void globalWarmingBFS(){
        visited = new boolean[N][M];
        for(int i=0; i<N; i++){
            for (int j = 0; j < M; j++) {
                if(!visited[i][j] && map[i][j] > 0){
                    bfs(i, j);
                }
            }
        }
    }
}