2 - 1. BFS 예제 (백준 7576번: 토마토)

백준 7576(토마토)

BFS 문제부터 가져왔습니다.

기본적인 BFS 문제이긴 하지만 약간의 발상의 전환이 필요한 문제라 정답율은 꽤 낮은편입니다.

구현은 인접 행렬(2차원 행렬)로 해야 할 것 같아요.

구현하기 전에 우선 토마토의 조건이 몇가지가 존재합니다.

조건 1

익은 토마토 주변에 덜 익은 토마토가 존재하는 경우: 다음날 덜 익은 토마토가 익은 토마토가 됨.

조건 2

토마토는 저절로 익지 않음

토마토가 하나라도 안 익는다면? -1 출력

조건 3

토마토의 갯수는 정해져있지 않다.

조건 1, 조건 2의 경우는 BFS나 DFS로 구현하면 될 것 같다는 느낌이 듭니다.

조건 3은 어떨까요? 이 문제가 어려워지는 조건이라고 볼 수 있겠네요.

같이 생각해 봅시다.

물론 토마토(익은 or 덜 익은)가 고정적으로 0개나 1개가 나온다면, 이는 처리하기가 매우 간단합니다.

반복문으로 돌려서 구분하면 되니까요.

하지만 익은 토마토와 덜 익은 토마토가 여러개 나온다면, 그리 간단한 문제는 아닙니다..

왜냐하면, 아래와 같은 구조로 토마토가 존재한다고 가정 해보겠습니다.

위와 같을때 모든 토마토가 익으려면 필요한 최소 시간은 얼마 일까요?

아마도 아래 처럼 동작하며 토마토가 익을 것이고 그러면...

총 8일이 걸리겠네요.

그런데 익은 토마토가 오른쪽 맨 아래에도 존재한다고 가정 해볼게요.

총 4일만에 끝나고 맙니다.

그래서 저 조건의 의미가 뭘까요.

탐색의 시작점이 한 두개가 아닐 수 도 있다는 소리입니다.

즉, 우리가 예시로 돌려봤던 프로그램은 무조건 시작점을 하나 정해놓고 돌렸는데..

이 문제는 그렇게 생각하면 문제가 상당히 꼬여버리게됩니다.

이미 알아 차린 분들도 계실겁니다.

저는 처음 풀 때 진짜 갖은 고생 다하면서 풀었던거같아요.

차근차근 생각해 봅시다.

이전 연습한 기본 코드

1. 시작점이 하나
2. 처음에 시작점 하나만 큐에 담음

현재의 문제

1. 시작점이 여러개
2. 처음에 시작점 하나만 큐에 담음(?)

1번 부터 조건이 차이나는데 2번은 똑같이 하기엔 뭔가 이상하죠?

시작점이 여러개니까 큐에 한번에 여러개를 담으면 안될까요?

안될 건 없습니다. 오히려 좋죠.

이렇게해도 과연 정확하게 탐색이 가능할까? 라고 의문이 생길 수 있습니다.

저번에 제가 해드렸던것 처럼 큐를 직접 그려서 하나씩 넣고 빼보시면 충분히 가능하다는 것을 확인하실 수 있습니다.

또한 어떤 토마토가 먼저 큐에 담겨야하지? 이런 의문도 생길 수도 있습니다.

이번 의문같은 경우엔 전혀 고려 대상이 아닙니다.

만약 아까처럼 왼쪽 위와 오른쪽 아래에 있는 토마토를 서로 순서를 다르게 넣는다고 생각해보세요.

노란색과 하늘색은 익은 토마토이고 진한 파란색은 이제 익어야 할 토마토입니다.

• 만약 왼쪽 위를 먼저 큐에 넣으면 노란색 토마토가 진한 파란색을 익도록 도와줄 것입니다.
• 오른쪽 아래를 먼저 큐에 넣으면 하늘색 토마토가 진한 파란색을 익도록 도와주게 됩니다.

이 문제에서 어떤 토마토가 익게 하느냐가 중요한건 아니죠?

최소 날짜만 구하면 되니까 우린 그 날짜에 대한 정보만 저장했다가 출력하면 된다는 얘기가 됩니다.

사실 조금만 생각해보시면 다 이해될만한 내용인데, 너무 길게 얘기를 한 것 같네요.ㅎㅎ

어쨌든 이제 이 내용을 통해 코드로 구현 해볼게요.

기본적인 구성은 거의 똑같습니다. 우선

1. 익은 토마토가 존재하는 곳의 정점을 따로 저장합니다.
2. 저장한 정점을 미리 큐에 모두 담아줍니다.
3. BFS 진행하면서 방문 배열의 값을 날짜로 생각하며 값을 더해줍니다.
4. 토마토가 안익은 날은 0일 이니, 결과에 -1을 해주면 답이 나옵니다.

STATE라는 상수 배열도 선언했는데요. 신경안쓰셔도 됩니다.

그저 {빈 공간(-1), 덜 익은(0), 익은(1)} 순서로 값을 담아 둔 배열입니다.

그리고 입력시에 미리 익은 토마토들을 큐에 담아놓았습니다.

우선 BFS 메소드부터 보여드릴게요.

7576번 BFS 메소드

private static int bfs(int n, int m, Queue<Point> q, int[][] map, int[][] visit, int count) {
    int maxDays = 1;
        
    while(!q.isEmpty()){
        Point current = q.poll();
            
        for(final int[] DIRECTION : DIRECTIONS){
            int nextRow = current.row + DIRECTION[ROW];
            int nextCol = current.col + DIRECTION[COL];
                
            if(nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < m){
                if(map[nextRow][nextCol] == STATE[1] && visit[nextRow][nextCol] == 0){
                    
                    q.offer(new Point(nextRow, nextCol));
                    map[nextRow][nextCol] = STATE[2];                                        // 익은것
                    visit[nextRow][nextCol] = visit[current.row][current.col] + 1; 
                    maxDays = Math.max(maxDays, visit[nextRow][nextCol]);                    // 최대 일수
                    count--;
                }
            }
        }
    }
        
    if(count == 0)    return maxDays -1;     // 다 익었으면 걸린 익는데 날짜를 출력 
    else return STATE[0];                    // 안익은게 있다면 -1 출력
}

왜 최대 날짜를 구하는지는 말 안해도 아실거라 믿습니다.

사실 최대 날짜가 아닌 최적의 조건으로 완전히 탐색이 끝났을 때 걸린 시간이니.. 헷갈리지 마세요.

또한 count 변수는 나중에 다시 탐색하지 않고 미리 토마토가 다 익었는지 확인하기위해 사용했습니다.

7576번 전체코드

package breadth_first_search;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
/**
 * 
 *     @author minchoba
 *    백준 7576번 : 토마토
 *
 *    @see https://www.acmicpc.net/problem/7576
 *
 */
public class Main {
    public static final String SPACE = " ";
    private static final int[] STATE = {-1, 0, 1};
    
    private static final int[][] DIRECTIONS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    private static final int ROW = 0;
    private static final int COL = 1;
    
    private static class Point {
        int row;
        int col;
 
        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), SPACE);
 
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
 
        int[][] map = new int[N][M];
        int[][] isVisited = new int[N][M];
        
        int raredCnt = 0;
        Queue<Point> queue = new LinkedList<>();
        
        for(int row = 0; row < N; row++){
            st = new StringTokenizer(br.readLine(), SPACE);
            
            for(int col = 0; col < M; col++){
                int tomato = Integer.parseInt(st.nextToken());
                
                if(tomato == STATE[0]) {
                    map[row][col] = STATE[0];
                }
                else if(tomato == STATE[1]) {
                    raredCnt++;
                }
                else {
                    map[row][col] = STATE[2];
                    queue.offer(new Point(row, col));
                    isVisited[row][col] = 1;
                }
            }
        }
        
        br.close();
        System.out.println(bfs(N, M, queue, map, isVisited, raredCnt));
    }
    
    private static int bfs(int n, int m, Queue<Point> q, int[][] map, int[][] visit, int count) {
        int maxDays = 1;
        
        while(!q.isEmpty()){
            Point current = q.poll();
            
            for(final int[] DIRECTION : DIRECTIONS){
                int nextRow = current.row + DIRECTION[ROW];
                int nextCol = current.col + DIRECTION[COL];
                
                if(nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < m){
                    if(map[nextRow][nextCol] == STATE[1] && visit[nextRow][nextCol] == 0){
                        
                        q.offer(new Point(nextRow, nextCol));
                        map[nextRow][nextCol] = STATE[2];
                        visit[nextRow][nextCol] = visit[current.row][current.col] + 1; 
                        maxDays = Math.max(maxDays, visit[nextRow][nextCol]);
                        count--;
                    }
                }
            }
        }
        
        if(count == 0)    return maxDays -1;
        else return STATE[0];
    }
}
 

제출 결과

이해안가는 것이나, 질문 또는 잘못된 부분은 댓글로 지적 부탁드려요. 감사합니다.

문제의 저작권은 백준 온라인 저지에 있습니다.