[Python/Java] 백준 2573 - 빙산 [BFS]

문제

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

 

해설

BFS를 이용하여 해결할 수 있었다. melting, multipartite 검사, BFS로 각 스텝을 구성하였다. 녹는 빙하에 대해서는 loop를 줄이기 위해 BFS에서 녹아야 하는 빙하의 좌표를 미리 입력받았다.

 

Python

from sys import stdin
from collections import deque


command = [[-1, 0], [0, -1], [0, 1], [1, 0]]


def bfs(graph: list, visited: list, start_x: int, start_y: int, melt_list: list):
    queue = deque()
    queue.append([start_x, start_y])
    visited[start_x][start_y] = True

    while queue:
        row, col = queue.popleft()

        for r, c in command:
            r_move = row + r
            c_move = col + c
            if graph[r_move][c_move] == 0:
                melt_list.append([row, col])

            if 0 <= r_move < len(graph) and 0 <= c_move < len(graph[0]):
                if not visited[r_move][c_move] and graph[r_move][c_move] > 0:
                    visited[r_move][c_move] = True
                    queue.append((r_move, c_move))


def is_multipartite(rows: int, cols: int, graph: list, melt_list: list):
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    count = 0

    for i in range(rows):
        for j in range(cols):
            if 0 < graph[i][j] and not visited[i][j]:
                bfs(graph, visited, i, j, melt_list)
                count += 1
                if 1 < count:
                    return True
    return False


def melting(rows: int, cols: int, graph: list):
    year = 0

    while True:
        melt_list = []
        if is_multipartite(rows, cols, graph, melt_list):
            return year
        if not melt_list:
            return 0

        for r, c in melt_list:
            if 0 < graph[r][c]:
                graph[r][c] -= 1

        year += 1


n, m = map(int, stdin.readline().split(" "))
graph = [list(map(int, stdin.readline().split(" "))) for _ in range(n)]
print(melting(n, m, graph))

 

Java

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

public class Main {
    static int[] command = {-1, 0, 0, -1, 0, 1, 1, 0}; 

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] condition = br.readLine().split(" ");
        int n = Integer.parseInt(condition[0]);
        int m = Integer.parseInt(condition[1]);

        int[][] graph = new int[n][m];

        for(int i = 0; i < n; i++) {
            String[] rows = br.readLine().split(" ");
            for(int j = 0; j < rows.length; j++) {
                graph[i][j] = Integer.parseInt(rows[j]);
            }
        }

        sb.append(melting(n, m, graph));
        System.out.println(sb);
    }

    public static void bfs(int[][] graph, boolean[][] visited, int startX, int startY, List<int[]> meltList) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startX, startY});
        visited[startX][startY] = true;

        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];

            for(int i = 0; i < 4; i++) {
                int rMove = row + command[i * 2];
                int cMove = col + command[i * 2 + 1];

                if(0 <= rMove && rMove < graph.length && 0 <= cMove && cMove < graph[0].length) {
                    if(graph[rMove][cMove] == 0) {
                        meltList.add(new int[]{row, col});
                    }
                    if(!visited[rMove][cMove] && 0 < graph[rMove][cMove]) {
                        visited[rMove][cMove] = true;
                        queue.add(new int[]{rMove, cMove});
                    }
                }
            }
        }
    }

    public static boolean isMultipartite(int[][] graph, boolean[][] visited, List<int[]> meltList) {
        int count = 0;

        for(int i = 0; i < graph.length; i++) {
            for(int j = 0; j < graph[0].length; j++) {
                if(0 < graph[i][j] && !visited[i][j]) {
                    bfs(graph, visited, i, j, meltList);
                    count++;
                    if(1 < count) { return true; }
                }
            }
        }
        return false;
    }

    public static int melting(int n, int m, int[][] graph) {
        int year = 0;

        while(true) {
            List<int[]> meltList = new ArrayList<>();
            if(isMultipartite(graph, new boolean[n][m], meltList)) {
                return year;
            }

            if(meltList.isEmpty()) { return 0; }

            for(int[] coords : meltList) {
                int r = coords[0];
                int c = coords[1];
                if(graph[r][c] > 0) {
                    graph[r][c]--;
                }
            }

            year++;
        }
    }
}