알고리즘/백준
[백준] 7576번 - 토마토
땀두
2022. 3. 21. 14:29


BFS를 이용한 탐색문제이다. 이 문제의 경우, 기존에는 각 좌표에 해당하는 visited 배열을 통해서 방문 여부를 판단하였는데, 그렇게 하지 않고 다음 좌표를 방문할 때, count값을 1 증가시키는 방식으로 진행하였다.
처음에 값이 1인 좌표를 찾고, 그 좌표를 시작으로 상하좌우의 값들을 범위가 맞는지와 값이 0인지 유무를 판단하여 0인 경우 큐에 저장하고, 계속 탐색을 진행한다. 이 때 큐에 저장 시 하루가 지난 것으로 판단하므로 count값을 1 증가시켜주고, 모든 탐색이 끝났을 때, 0이 존재하면 -1을, 그렇지 않은 경우는 count값을 출력하도록 하였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static class Node {
int x;
int y;
int cnt;
Node(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
}
public static int[] nx = { -1, 0, 0, 1 };
public static int[] ny = { 0, 1, -1, 0 };
public static int[][] ary;
public static int x;
public static int y;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
y = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
ary = new int[x][y];
for (int i = 0; i < x; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < y; j++) {
ary[i][j] = Integer.parseInt(st.nextToken());
}
}
bfs();
}
public static void bfs() {
Queue<Node> q = new LinkedList<>();
int cnt = 0;
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
if (ary[i][j] == 1) {
Node n = new Node(i, j, 0);
q.add(n);
}
}
}
while (!q.isEmpty()) {
Node node = q.poll();
cnt = node.cnt;
for (int i = 0; i < 4; i++) {
int X = node.x + nx[i];
int Y = node.y + ny[i];
if (X >= 0 && X < x && Y >= 0 && Y < y) {
if (ary[X][Y] == 0) {
ary[X][Y] = 1;
q.add(new Node(X, Y, cnt + 1));
}
}
}
}
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
if (ary[i][j] == 0) {
System.out.println(-1);
return;
}
}
}
System.out.println(cnt);
}
}