일단 시작해보는 블로그

[알고리즘_풀이] 백준 - 토마토 java 본문

CS/알고리즘 풀이

[알고리즘_풀이] 백준 - 토마토 java

사용자 Selina Park 2020. 3. 11. 19:04

https://www.acmicpc.net/problem/7576

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마

www.acmicpc.net

import java.util.*;

public class Main {
	static int answer = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int M = sc.nextInt(); // 가로, j
		int N = sc.nextInt(); // 세로, i
		
		Node[][] a = new Node[N][M];
		Queue<Node> queue = new LinkedList<>();
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				int input = sc.nextInt();
				a[i][j] = new Node(i, j, input);
				if(input == 1) {
					queue.add(a[i][j]);
					a[i][j].level = 0;
				}
			}
		}
		
		bfs(a, queue, M, N);
		
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(a[i][j].value == 0) {
					answer = -1;
					break;
				}
			}
		}
		
		System.out.println(answer);
	}
	
	static void bfs(Node[][] a, Queue<Node> queue, int M, int N) {
		int[] di = {-1, 0, 1, 0};
		int[] dj = {0, 1, 0, -1};
		
		while(!queue.isEmpty()) {
			Node out = queue.remove();
			for(int k=0; k<4; k++) {
				int i = di[k] + out.yi;
				int j = dj[k] + out.xj;
				
				if(i<0 || i>=N || j<0 || j>=M) continue;
				
				if(a[i][j].value == 0) {
					queue.add(a[i][j]);
					a[i][j].level = out.level+1;
					a[i][j].value = out.level+1;
					answer = out.level+1;
				}
			}
		}
	}
	
	static class Node {
		int yi;
		int xj;
		int value;
		int level;
		
		Node(int yi, int xj, int value) {
			this.yi = yi;
			this.xj = xj;
			this.value = value;
			this.level = 0;
		}
	}

}

bfs

0 Comments
댓글쓰기 폼