https://www.acmicpc.net/problem/7569
7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net
형제 문제
https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
import java.io.*;
import java.util.*;
public class Main
{
static int n;
static int m;
static int h;
static int[][][] map;
static boolean[][][] visited;
public static int bfs(Queue<Node> q){
int[] move_h = {0, 0, 0, 0, 1, -1};
int[] move_r = {1, -1, 0, 0, 0, 0};
int[] move_c = {0, 0, 1, -1, 0, 0};
int step=0;
while(q.size()>0){
// System.out.println(q);
Node node = q.poll();
step=node.step;
for(int i=0;i<6;i++){
Node next = new Node(node.h+move_h[i],node.r+move_r[i],node.c+move_c[i],node.step+1);
if(next.h>=0 && next.r>=0 && next.c>=0 && next.h< h && next.r< n && next.c < m){
if(!visited[next.h][next.r][next.c] && map[next.h][next.r][next.c]==0){
visited[next.h][next.r][next.c] = true;
q.offer(next);
}
}
}
}
return step;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input1 = br.readLine().split(" ");
m = Integer.parseInt(input1[0]);
n = Integer.parseInt(input1[1]);
h = Integer.parseInt(input1[2]);
map = new int[h][n][m];
visited = new boolean[h][n][m];
Queue<Node> q = new LinkedList();
boolean exist_0 = false;
for(int i=0;i<h;i++){
for(int j=0; j<n;j++){
String[] temp = br.readLine().split(" ");
for(int k=0;k<m;k++){
map[i][j][k] = Integer.parseInt(temp[k]);
if(map[i][j][k]==1){
q.offer(new Node(i,j,k,0));
visited[i][j][k] = true;
}
if(map[i][j][k]==0){
exist_0=true;
}
}
}
}
if(q.size()==0 && exist_0){
System.out.println(-1);
return;
}
int ans = bfs(q);
for(int i=0;i<h;i++){
for(int j=0; j<n;j++){
for(int k=0;k<m;k++){
if(!visited[i][j][k] && map[i][j][k]==0){
System.out.println(-1);
return;
}
}
}
}
System.out.println(ans);
}
public static class Node{
int r;
int c;
int h;
int step;
public Node(int h, int r ,int c ,int step){
this.r = r;
this.c = c;
this.h = h;
this.step = step;
}
public String toString(){
return "["+h+", "+r+", "+c+", "+step+" ]";
}
}
}
7576의 코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Main {
static int n, m;
static int[][] board;
static int[][] visited;
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
board = new int[n][m];
visited = new int[n][m];
Queue<Point> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
board[i][j] = sc.nextInt();
if (board[i][j] == 1) {
q.add(new Point(i, j));
visited[i][j] = 1;
}
}
}
while (!q.isEmpty()) {
Point now = q.poll();
for (int i = 0; i < 4; i++) {
int nr = now.r + dr[i];
int nc = now.c + dc[i];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
if (visited[nr][nc] == 0 && board[nr][nc] == 0) {
visited[nr][nc] = visited[now.r][now.c] + 1;
q.add(new Point(nr, nc));
}
}
}
int max = 0;
boolean yummy = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
max = Math.max(max, visited[i][j]);
if (visited[i][j] == 0 && board[i][j] == 0) {
yummy = false;
break;
}
}
}
if (yummy) System.out.println(max - 1);
else System.out.println(-1);
}
}
class Point {
int r, c;
public Point(int r, int c) {
this.r = r;
this.c = c;
}
}
'Problem Solving > BFS' 카테고리의 다른 글
BOJ9019 DSLR (0) | 2024.03.11 |
---|---|
BOJ5427 불 (0) | 2024.03.11 |
BOJ7562 나이트의 이동 (0) | 2024.03.10 |
BOJ 12851 숨바꼭질2 (0) | 2024.03.10 |
BOJ1697 숨바꼭질 (0) | 2024.03.10 |