BOJ07576 토마토

https://www.acmicpc.net/problem/7576 (opens new window)

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익는다.

Location.java

좌표를 관리하기 위한 Location 클래스이다.

private static class Location {
    private int x; 
    private int y;
    
    public Location(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

BFS 활용

주변 토마토를 익게 하기 위한 bfs 메소드이다. 만약 익은 토마토가 여러개 인 경우 하루가 지나면 동시 다발적으로 주변 토마토를 익게 만들 것이다. 그렇기 때문에 bfs가 시작하는 시점에 익은 토마토를 모두 queue에 저장한다.

private static void bfs() {
    Queue<Location> queue = new LinkedList<>();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (graph[i][j] == 1) {
                queue.add(new Location(i, j));
            }
        }
    }

    while (!queue.isEmpty()) {
        Location location = queue.poll();
        for (int i = 0; i < 4; i++) {
            int x = location.x + dx[i];
            int y = location.y + dy[i];

            if (isLocation(x, y)) {
                queue.add(new Location(x, y));
                graph[x][y] = graph[location.x][location.y] + 1;
            }
        }
    }
}

private static boolean isLocation(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || graph[x][y] != 0) {
        return false;
    }
    return true;
}

제출 코드

위에서 작성한 bfs를 활용하면 토마토가 전부 탐색되며 익힌 날짜를 늘려간다. 이때 전체 탐색하며 가장 큰 값을 뽑아낸다.

private static int getMax() {
    int max = Integer.MIN_VALUE;
    for (int[] ints : graph) {
        for (int anInt : ints) {
            if (anInt == 0) {
                return -1;
            }

            max = Math.max(anInt, max)a;
        }
    }

    return max - 1;
}

아래는 최종 제출 코드이다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ7576 {

    private static int m, n;
    private static int[][] graph;

    // 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};

    private static class Location {
        int x; int y;
        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static void bfs() {
        Queue<Location> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j] == 1) {
                    queue.add(new Location(i, j));
                }
            }
        }

        while (!queue.isEmpty()) {
            Location location = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = location.x + dx[i];
                int y = location.y + dy[i];

                if (isLocation(x, y)) {
                    queue.add(new Location(x, y));
                    graph[x][y] = graph[location.x][location.y] + 1;
                }
            }
        }
    }

    private static boolean isLocation(int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || graph[x][y] != 0) {
            return false;
        }
        return true;
    }

    private static int getMax() {
        int max = Integer.MIN_VALUE;
        for (int[] ints : graph) {
            for (int anInt : ints) {
                if (anInt == 0) {
                    return -1;
                }

                max = Math.max(anInt, max);
            }
        }

        return max - 1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        m = scanner.nextInt(); // 가로
        n = scanner.nextInt(); // 세로

        graph = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }

        bfs();

        System.out.println(getMax());
    }
}

#algorithm #BOJ #그래프 이론 #그래프 탐색 #너비 우선 탐색 #BFS