[백준]7576_토마토(bfs/dfs)

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

7576번: 토마토

문제

• M x N 상자가 주어진다.
• 0 : 익지 않은 토마토
• 1 : 익은 토마토
• -1 :  토마토가 없는 칸

풀이

• 퍼져나가므로 bfs가 더 맞을 것 같다.

bfs 구현

  while (!q.isEmpty()) {

            Pair now = q.poll(); // 큐의 맨앞 
            int nowx = now.x;  //현재 토마토 x값
            int nowy = now.y;  //현재 토마토 y값 
            for (int i = 0; i < 4; i++) {
                int nextX = nowx + dx[i];
                int nextY = nowy + dy[i];

                //범위 밖 패스
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }
                
                if (arr[nextX][nextY] != 0) {
                    continue;
                }
                //다음값 = 현재 일수 + 1
                arr[nextX][nextY] = arr[nowx][nowy] + 1;
                q.add(new Pair(nextX, nextY));
            }
        }

답 도출

• 토마토 상자에서 가장 큰 숫자를 출력
• 토마토 상자에 만약 0이 있다면 (익지 못한 상황) -1 출력 종료

  int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 0) {
                    //토마토가 모두 익지 못한 상황이라면 -1 을 출력한다.
                    System.out.println(-1);
                    return;
                }
                max = Math.max(max, arr[i][j]);
            }
        }
        //그렇지 않다면 최대값을 출력한다.
        System.out.println(max - 1);