Problem Solving/BFS

BOJ7569 토마토

윤재에요 2024. 3. 11. 15:51

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;
    }
}