7576번

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

7576번: 토마토

이번 문제는 접근을 아예 못할 것은 아니였지만 접근 과정에서 N,M을 정하는게 헷갈리고, 동시에 여러 곳에서 탐색이 진행되야 한다는 것에서 구현을 하는 것에 어려움이 있었다.

그래서 결국 질문 게시판에서 다른 사람들의 접근 방식을 봐버렸다...

이 문제의 접근 방법은 다음과 같다. 일단 익어있는 모든 토마토의 좌표를 큐에 집어넣어서 탐색을 시작하는 것이다.

그렇게 되면 동시에 탐색을 진행하는 것과 마찬가지가 된다.

왜냐하면 다른 문제의 해결 방법과 마찬가지로 내부 카운팅을 하기 때문에 양쪽에서 같은 카운팅으로 좌표를 채운다고 생각 할 수 있다고 보기 때문이다.

예를 들어 아래처럼 생긴 표를 그릴 수 있다.

1	2	3	4	4
2	3	4	4	3
3	4	4	3	2
4	4	3	2	1

(1,1)과 (5,4)에서 동시에 탐색을 진행하여 칸을 채우기 때문이다.

그리고 토마토가 모두 익는 최단기간을 구하라고 했다. 그렇기 때문에 이 문제는 BFS로 풀어야한다.

 

따라서 탐색을 시작할 때 큐에 모든 토마토가 익은 좌표들을 넣고, 나머지는 다른 문제들과 동일하게 탐색을 진행한다.

그렇기에 BFS 탐색 메서드를 구현하면 아래와 같이 나온다.

이 메서드를 구현하면서 헷갈렸던 것은 x,y좌표와 N,M좌표를 맞추는 것이었다..

다른 사람들은 어떤지 모르지만 선형대수를 공부하면서 N(세로) by M(가로) 행렬로 공부했던터라 더욱 헷갈렸다..

 

public void bfs(){
        int cnt = 0;
        for(int i=0; i<M; i++){
            for(int j=0; j<N; j++){
                if(table[i][j]==1){
                    visit[i][j]=true;
                    queue.add(new target(j,i,cnt));
                }
            }
        }
        int max = Integer.MIN_VALUE;
        while (!queue.isEmpty()){
            target tmp = queue.poll();
            if(tmp.cnt>max){
                max = tmp.cnt;
            }
            for(int i=0; i<4; i++){
                int x = tmp.x+dx[i];
                int y = tmp.y+dy[i];
                if(x>=0&&y>=0&&x<N&&y<M&&table[y][x]==0){
                    table[y][x]=1;
                    queue.add(new target(x,y, tmp.cnt+1));
                }
            }
        }
        day = max;
    }
}

결과적으로 모든 탐색을 끝내고 나왔을 때 만약 익지 않은 토마토가 있다면, -1을 출력하여 모든 토마토가 익을 수 없음을 반환해주면 된다.

그럼 이 문제의 구현은 끝이 난다. 추가로 방문처리는 1로 해주었다. 그리고 원래부터 토마토가 없어서 -1인 부분은 큐에 들어갈 수 없음으로 0인 경우만 큐에 넣도록 조건을 넣었다.

 

 

정답코드는 아래와 같다.

package backjoon.b7576;

import java.util.LinkedList;
import java.util.Queue;
import java.io.*;
import java.util.*;
public class b7576 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] table=new int[M][N];
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                table[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        Graph g = new Graph(N,M,table);
        g.bfs();
        int day = g.day;
        for(int[] i : g.table){
            for(int j : i){
                if(j==0){
                    day = -1;
                }
            }
        }
        System.out.println(day);
    }
}
class Graph{
    int N;
    int M;
    int day;
    int[][] table;
    int[] dx = {1,0,-1, 0};
    int[] dy = {0,1, 0,-1};
    Queue<target> queue;
    public Graph(int n, int m, int[][] table) {
        N = n;
        M = m;
        this.table = table;
        queue = new LinkedList<>();
    }
    public void bfs(){
        int cnt = 0;
        for(int i=0; i<M; i++){
            for(int j=0; j<N; j++){
                if(table[i][j]==1){
                    queue.add(new target(j,i,cnt));
                }
            }
        }
        int max = Integer.MIN_VALUE;
        while (!queue.isEmpty()){
            target tmp = queue.poll();
            if(tmp.cnt>max){
                max = tmp.cnt;
            }
            for(int i=0; i<4; i++){
                int x = tmp.x+dx[i];
                int y = tmp.y+dy[i];
                if(x>=0&&y>=0&&x<N&&y<M&&table[y][x]==0){
                    table[y][x]=1;
                    queue.add(new target(x,y, tmp.cnt+1));
                }
            }
        }
        day = max;
    }
}
class target{
    int x;
    int y;
    int cnt;

    public target(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}