[BOJ][7576] 토마토

1. 문제 링크

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

2. 사용 알고리즘

BFS

3. 풀이

단계별로 진행한다는 BFS의 성질을 이용

1) 토마토를 저장하는 arr 배열, 이동 거리 및 방문여부를 저장하기 위한 dist 배열 선언

2) arr의 값이 1인 경우(익은 토마토인 경우) Queue에 해당 인덱스 저장 후 거리를 0으로 저장하고, arr의 값이 1이 아닌 경우 거리를 -1로 저장

3) Queue를 순회하며 상하좌우 좌표를 비교하여 토마토가 아직 익지 않았고, 거리가 -1인 경우 Queue에 저장하고, 해당 토마토의 거리를 현재 토마토의 거리 + 1로 저장

4) 3)의 과정을 반복하며 BFS 탐색 완료

5) 가장 큰 거리를 출력하는데, 만약 익지 않은 토마토가 존재하는 경우 -1 출력

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/7576.cpp

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int m, n;
int arr[1003][1003];
int dist[1003][1003];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
queue<pair<int, int>> q;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> m >> n;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            cin >> arr[i][j];
            dist[i][j] = -1;
            if(arr[i][j] == 1) {
                q.push(make_pair(i, j));
                dist[i][j] = 0;
            }
        }
    }
    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for(int i = 0; i < 4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(1 <= ny && ny <= n && 1 <= nx && nx <= m) {
                if(arr[ny][nx] == 0 && dist[ny][nx] == -1) {
                    q.push(make_pair(ny, nx));
                    dist[ny][nx] = dist[y][x] + 1;
                }
            }
        }
    }
    int ans = 0, flag = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(ans < dist[i][j]) ans = dist[i][j];
            if(arr[i][j] == 0 && dist[i][j] == -1) flag = 0;
        }
    }
    cout << (flag ? ans : -1) << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/7576.java

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

class Pair {
    int y, x;
    Pair(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Main {

    static int m, n;
    static int arr[][] = new int[1003][1003];
    static int dist[][] = new int[1003][1003];
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, -1, 0, 1};
    static Queue<Pair> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        for(int i = 1; i <= n; ++i) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= m; ++j) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                dist[i][j] = -1;
                if(arr[i][j] == 1) {
                    q.add(new Pair(i, j));
                    dist[i][j] = 0;
                }
            }
        }
        while(!q.isEmpty()) {
            Pair p = q.remove();
            for(int i = 0; i < 4; ++i) {
                int ny = p.y + dy[i];
                int nx = p.x + dx[i];
                if(1 <= ny && ny <= n && 1 <= nx && nx <= m) {
                    if(arr[ny][nx] == 0 && dist[ny][nx] == -1) {
                        q.add(new Pair(ny, nx));
                        dist[ny][nx] = dist[p.y][p.x] + 1;
                    }
                }
            }
        }
        int ans = 0, flag = 1;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                if(ans < dist[i][j]) ans = dist[i][j];
                if(arr[i][j] == 0 && dist[i][j] == -1) flag = 0;
            }
        }
        System.out.println((flag == 1) ? ans : -1);
    }
}