Hyemi Lee

Hyemi Lee

주니어 개발자의 삽질과 기록

Algorithm, boj, 7576(토마토)

  • DFS

    풀이

  • 과일판에서 익어있는 과일의 위치를 찾아 큐에 넣는다
  • 다음날, 전날 익은 과일의 개수만큼 큐에서 과일위치를 꺼낸다
  • 꺼낸 위치에서 안익은 과일의 위치를 찾아 익히고 큐에 넣는다
  • 큐가 빌때까지 반복한다
package org.baekjoon;
import java.util.*;
public class test7576 {
	static boolean[][] visited;	// 방문여부
	static int[][] fruit;		// 과일판
	static int M,N;				// 과일 열, 행
	static int todayCnt = 0; 	// 오늘 익은 과일수
	static int[] Dx = {-1, 1, 0, 0};
	static int[] Dy = {0, 0, -1, 1};
	public static void main(String[] args) {
		// 과일 정보 입력받기
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		visited = new boolean[N][M];
		fruit = new int[N][M];
		for (int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				fruit[i][j] = sc.nextInt();
			}
		}
		Queue<dot> qu = new LinkedList<dot>();
		// 처음 1 의 위치 찾기
		for (int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(fruit[i][j] == 1) {
					qu.offer(new dot(i,j));
					visited[i][j] = true;
					todayCnt++;
				}
			}
		}
		// 익은 과일 하나도 없음 끝.
		if(todayCnt == 0 )
			System.out.println(-1);
		// 모두 익은 과일이라면
		else if(todayCnt == (M*N))
			System.out.println(0);
		else
			bfs(qu);
	}
	static void bfs(Queue<dot> qu) {
		int day = -1;
		int yesterdayCnt;					// 전날 익은 과일 개수
		while ( !qu.isEmpty()) {			// 큐 : 전날익은 과일위치
			yesterdayCnt = todayCnt;
			todayCnt = 0;
			// 전날 익은 과일을 모두 꺼낸다.
			for (int i=0; i<yesterdayCnt; i++) {
				dot Cq = qu.poll();
				// 해당과일의 상하좌우 과일을 확인한다.
				for (int j=0; j<4; j++) {
					int Nx = Cq.x + Dx[j];
					int Ny = Cq.y + Dy[j];
					// 상하좌우가 과일상자 범위 안에 있어야 한다.
					if (0 > Nx || Nx >= N || 0 > Ny || Ny >= M )
						continue;
					// 이미 방문했다면 패쓰.
					if (visited[Nx][Ny] == true )
						continue;
					visited[Nx][Ny] = true;
					// 안익은 과일이라면 익히고, 큐에 넣고, 오늘익은 과일수 +1
					if (fruit[Nx][Ny] == 0) {
						fruit[Nx][Ny] = 1;
						qu.offer(new dot(Nx, Ny));
						todayCnt++;
					}
				}
			}
			day++;
		}
		boolean is_done = true;
		// 과일판에 안익은 과일이 있으면, -1
		for (int i=0; i<N; i++) {
			for(int e:fruit[i]) {
				if(e == 0) {
					System.out.println(-1);
					is_done = false;
					break;
				}
			}
		}
		if(is_done == true)
			System.out.println(day);
	}
}
class dot {
 int x,y;
 dot (int x, int y){
 this.x = x;
 this.y = y;
 }
}

Reference

문제로 가기

Share on

Twitter Facebook LinkedIn

You may also enjoy

Redis Stream

2021年04月28日

Stream Stream은 로그 데이터를 처리하게위해 5.0에서 새로 도입된 데이터 타입입니다. 대량의 데이터가 연속적으로 발생할때 처리하기 위해 등장했습니다. 기존 데이터를 수정하지 않고 오직 추가로 발생합니다. 이런 종류의 데이터를 stream or log데이터...

Study, Object, chapter2&3 presentation

2021年04月20日

chapter03. 역할, 책임, 협력 객체지향 설계란, 올바른 객체에게 올바른 책임을 할당하면서 낮은 결합도와 높은 응집도를 가진 구조를 창조하는 활동이다.

Spring, chatting 프로그램 만들기, Reactive란?

2020年06月16日

Reactive 막힘없이 흘러다니는 data(event)를 통해 사용자에게 자연스러운 응답을 주고 규모 탄력적으로 리소스를 사용하며 실패에 있어서 유연하게 대처한다 모든 지점에서 블럭 되지 않게 하자 oop와 같은 패러다임 모든 것을 비동기적인 data의 strea...