[백준] 7576 토마토 풀이

창고에 보관되는 토마토가 인접하면 서로 익는다고 한다. BFS로 풀면 되는 문제이지만 BFS문제마다 하나씩 포인트가 있다. 이 문제는 한 점에서만 탐색이 이루어지는 것이 아니라 동시에 여러 곳에서 BFS가 일어난다. 상자 안에 토마토가 여러개 있을 수 있으므로 각 지점부터 BFSF를 진행해 주어야 한다. 그래서 배열을 초기화 하는 과정에서 토마토가 들어 있다면 큐에 하나씩 넣어주어야 한다. 

전체 소스

import java.util.*;

import java.io.*;

public class Q7576 {

static int row;

static int col;

static int[][] tomato;

static int[] moveX = {0, -1, 0, 1};

static int[] moveY = {-1, 0, 1, 0};

public static void main(String[] args) throws IOException {

// 입력

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String[] condition = br.readLine().split(" ");

col = Integer.valueOf(condition[0]);

row = Integer.valueOf(condition[1]);

tomato = new int[row][col];

Queue<Pos> q = new LinkedList<>();

for (int i = 0; i < row; i++) {

String[] input = br.readLine().split(" ");

for (int j = 0; j < col; j++) {

tomato[i][j] = Integer.parseInt(input[j]);

if (tomato[i][j] == 1) {

q.add(new Pos(i, j));

}

}

}

if (q.size() != 0) {

while (!q.isEmpty()) {

Pos polledPos = q.poll();

int x = polledPos.x;

int y = polledPos.y;

for (int k = 0; k < 4; k++) {

int moveI = x + moveX[k];

int moveJ = y + moveY[k];

if (0 <= moveI && moveI < row && 0 <= moveJ && moveJ < col) {

if (tomato[moveI][moveJ] == 0) {

tomato[moveI][moveJ] = tomato[x][y] + 1;

q.add(new Pos(moveI, moveJ));

}

}

}

}

} else {

System.out.println(-1);

System.exit(0);

}

int ans = -1;

for (int i = 0; i < row; i++) {

for (int j = 0; j < col; j++) {

if(tomato[i][j] == 0) {

System.out.println(-1);

System.exit(0);

}

if (tomato[i][j] > ans) {

ans = tomato[i][j];

}

}

}

System.out.println(ans - 1);

}

}

class Pos {

int x;

int y;

public Pos(int x, int y) {

this.x = x;

this.y = y;

}

}