반응형
창고에 보관되는 토마토가 인접하면 서로 익는다고 한다. 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;
}
}
반응형
'프로그래밍 > Algorithm' 카테고리의 다른 글
[백준] 11279 최대 힙 풀이 (0) | 2019.01.31 |
---|---|
[백준] 11052번 카드 구매하기 (0) | 2019.01.11 |
[백준 알고리즘] 2156 - 포도주 시식 (0) | 2018.11.19 |
[프로그래머스] 모의고사 (0) | 2018.10.21 |
[프로그래머스] K번째 수 (0) | 2018.10.21 |