[Java] 백준 7576번 : 토마토 <Gold 5>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

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

7576번: 토마토

Code

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    class tomato{
        int x;
        int y;
        tomato(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    void run() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Queue<tomato> queue = new LinkedList<>();
        String[] input = bf.readLine().split(" ");
        int M = Integer.parseInt(input[0]);
        int N = Integer.parseInt(input[1]);

        int[][] graph =  new int[N][M];
        for(int i = 0; i < N; i++){
            input = bf.readLine().split(" ");
            for(int j = 0; j < M; j++){
                graph[i][j] = Integer.parseInt(input[j]);
                if(graph[i][j] == 1){
                    queue.add(new tomato(i,j));
                }
            }
        }

        System.out.println(BFS(graph, queue));
    }

    int BFS(int[][] graph, Queue<tomato> queue){
        int max = 0;
        while (!queue.isEmpty()){
            int[] dx = {0,0,1,-1};
            int[] dy = {1,-1,0,0};

            tomato xy = queue.poll();
            int x = xy.x;
            int y = xy.y;

            for(int i = 0; i < 4; i++){
                int xx = x + dx[i];
                int yy = y + dy[i];
                if(xx >= 0 && xx < graph.length && yy >= 0 && yy < graph[x].length){
                    if(graph[xx][yy] == 0){
                        queue.add(new tomato(xx,yy));
                        graph[xx][yy] = graph[x][y] + 1;
                        if(max<graph[xx][yy]){
                            max = graph[xx][yy];
                        }
                    }
                }
            }
        }

        for(int i = 0; i < graph.length; i++){
            for(int j = 0; j < graph[i].length; j++){
                if(graph[i][j] == 0){
                    return -1;
                }
            }
        }

        if(max == 0){
            return 0;
        }

        return max-1;
    }

    public static void main(String[] args) throws IOException{
        Main my = new Main();
        my.run();
    }
}

---

Code 필수 요소

1. BFS

2. 조건 설정

 

이것만 생각해내면 절반은 끝났다.

 

// BFS

이번 문제는 BFS를 사용했다.

이 문제는 BFS를 선택한 이유가 있다.

해당 문제는 익은 토마토부터 안익은 토마토까지의 최단 거리를 구해야 한다. 그렇기때문에 최단거리를 구할 수 있는 알고리즘인 BFS를 사용했다. DFS는 최단 거리를 구하는데 적합하지 않은 알고리즘이다.

 

// 조건 설정

내가 작성한 조건은 이렇다.

1. 그래프의 범위를 나가지 않도록 xx와 yy의 위치를 if문으로 확인

2. 탐색이 종료되었을 경우 0이 존재하면 -1 리턴

3. 그래프 내에 0이 존재하지 않을경우, 즉 모든 토마토가 익어있을경우 0 리턴

4. 정상적으로 탐색했을경우 최댓값 -1 리턴

 

// 전체적 설명

class tomato를 만들어줘서 배열에 x,y좌표 모두를 넣을 수 있도록 해줬다.

그 후 값을 넣을때 1이 존재한다면 큐에 넣어줘서 양방향에서 동시에 진행하여 최단 횟수를 구할 수 있도록 했다.

 

글고 딴사람들 코드보니까 dx랑 dy를 만들어서 for문으로 상하좌우 값을 확인하더라. 난 저번문제 하드코딩으로 했는데...

이게 더 좋아보여서 나도 이렇게 이번에 짜봤다. 아 순서가 왜저렇냐고? 굳이 상하좌우 이쁘게 안해도 될거같아서 걍 했다. 귀찮아.

 

탐색이 종료됐을때 0이 존재한다? => 해당 값까지 도달하지 못한다 => -1로 가는길이 막혀있다.

이걸 생각하기 힘들었다. 무조건 -1을 만나서 해당 구역을 못가는 경우를 체크해야한다고 생각했는데 그냥 탐색이 끝났을때 0이 있으면 가는길이 막혀있는거였다...

 

max라는 변수를 이용해서 최단 거리를 구하는 방식을 썼다. 이때, max가 0이라면 한번도 큐의 값이 0이었다는 적이 없는거니까 존재하는 모든 토마토가 익어있단 뜻이므로 0을 리턴했다.

 

그리고 max-1을 리턴한 이유는 시작값이 1이기 때문에 총 일수 보다 1이 많다. 그래서 빼줌

 

 

DFS와 BFS란?

https://naemamdaelo.tistory.com/37

알고리즘 - 깊이우선탐색(DFS), 너비우선탐색(BFS)

 

x좌표랑 y좌표랑 동시에 큐에 넣는 방법을 생각하는게 힘들었다. 뭔가... 배열로 넣자니 이상하고 각각 넣자니 그것도 그거대로 이상하고...

순서대로 x넣고 y넣어서 하나씩 빼버려...? 하다가 C언어 구조체 생각나서 클래스 만들었는데 이게 더 나은거 같다.

이 문제는 정말 쉬운데 그 쉬운 방법을 생각하는게 힘든거 같다. 실제로 코드보면 진짜 간단한데 이걸 생각하는데 꽤나 걸렸다.

 

 

-꿑-