[백준-java] 토마토 7576번 7569번

알고리즘 : BFS

토마토 시리즈로서 2차원인 7576번과 3차원인 7569번을 설명하도록 하겠다.

---

문제설명 : 7576번 토마토

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

링크 참조 

---

내 풀이

 

이 문제는 시작점이 여러개 일경우의 BFS 문제이다.

문제에서도 주어진 것처럼 토마토의 위치가 여러군데에서 시작하고

BFS를 따로따로 진행하면 dist배열 초기화가 먼저 이루어져서 겹치는 부분에 대해 처리가 정확히 되지 않는다.

간단하게 이 문제를 풀이하면 시작점들을 큐에 집어넣고 BFS를 시작하면 된다.

왜냐하면 큐의 특성상 FIFO 이므로 시작점들을 넣고 BFS를 돌리면 순차적으로 각 시작점 위치에서 BFS가 돌아가면서 실행이 되기 때문이다. 큐의 특성으로 거리순으로 저장되는 것 

만약에 스택이였으면 하나의 시작점이 끝날때까지 다른 시작점이 시작 못했을 거지만 큐이기에 가능하다.

 

별다를거 없는 BFS 문제이고 특이 한것은 토마토가 익지 않았을 경우와 모두 익었을 경우에 대해서 예외처리인데

토마토가 익지 않은 즉 실패한 상황은 dist배열에 -1이 갱신 되지 않은 상태이므로 이경우에대해서 쉽게 처리 가능하다.

또한 모두 익었을 경우 역시 dist배열이 모두 0일 것이므로 Max함수로 answer을 업데이트해도 0 으로 유지함으로써 처리가 가능하다.

import java.io.*;
import java.util.*;

public class Main {
	static class Node {
		int x ;
		int y;
		public Node(int x,int y) {
			this.x = x;
			this.y = y;
		}
	}
	private static int[][] board;
	private static int[][] dist;
	private static int[] dx = {1,-1,0,0};
	private static int[] dy = {0,0,1,-1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		board = new int[N][M];
		dist = new int[N][M];
		ArrayDeque<Node> q = new ArrayDeque<>();
		// 입력 초기화 및 시작점 큐에 넣기
		for (int i = 0; i < N ;i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0 ; j < M; j++) {
				int value = Integer.parseInt(st.nextToken());
				board[i][j] = value;
				if (value == 1) q.offer(new Node(i,j));
				if (value == 0) dist[i][j] = -1;
			}
		}
		// 각 시작점에서 BFS 시작 
		// 모든 토마토가 익어있다는 것은 1이거나 -1로 찬 상태 그러면 dist값은 전부 0 일거임 
		// 토마토가 모두 익지 못했다는 것 역시 0인 자리에 -1 이 저장되있으므로 -1 이면 -1 출력
		while(!q.isEmpty()) {
			Node cur = q.poll();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];
				if (nx <0 || nx >= N || ny <0 || ny >=M) continue;
				if (board[nx][ny] != 0 || dist[nx][ny] > 0) continue;
				dist[nx][ny] = dist[cur.x][cur.y] +1 ;
				q.offer(new Node(nx,ny));
			}
		}
		int answer = 0 ;
		for (int i =0; i< N; i++) {
			for (int j = 0; j<M;j++) {
				if (dist[i][j] == -1) {
					System.out.println(-1);
					return ;
				}
				answer = Math.max(answer,dist[i][j]);
			}
		}
		System.out.println(answer);
	}
}

---

 

문제설명 : 토마토 7569번 

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

3차원 문제

 

---

내 풀이

 

3차원의 BFS로 dh 방향을 추가하면 된다.

풀이 방식은 똑같다

 

import java.util.*;
import java.io.*;

class Main {
	static class Node {
		int x;
		int y;
		int h;
		public Node(int x,int y,int h) {
			this.x = x;
			this.y = y;
			this.h = h;
		}
	}
	private static int[] dx = {1,-1,0,0,0,0};
	private static int[] dy = {0,0,1,-1,0,0};
	private static int[] dh = {0,0,0,0,1,-1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int H = Integer.parseInt(st.nextToken());
		
		int[][][] board = new int[N][M][H];
		int[][][] dist = new int[N][M][H];
		ArrayDeque<Node> q = new ArrayDeque<>();
		// 초기화
		for (int i = 0 ; i< H;i++) {
			for (int j = 0; j<N;j++) {
				st = new StringTokenizer(br.readLine());
				for (int k= 0; k<M;k++) {
					int value = Integer.parseInt(st.nextToken());
					board[j][k][i] = value;
					if (value == 1) q.offer(new Node(j,k,i));
					if (value == 0) dist[j][k][i] = -1;
				}
			}
		}
		
		// bfs 6방향으로 진행 
		while(!q.isEmpty()) {
			Node cur = q.poll();
			for (int dir = 0; dir < 6;dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];
				int nh = cur.h + dh[dir];
				if (nx < 0 || nx >= N || ny <0 || ny >= M || nh < 0 || nh >= H) continue;
				if (board[nx][ny][nh] !=0 || dist[nx][ny][nh] >0 ) continue;
				dist[nx][ny][nh] = dist[cur.x][cur.y][cur.h] +1;
				q.offer(new Node(nx,ny,nh));
			}
		}
		// 순회하며 -1 이면 -1 출력 return
		int answer = 0;
		for (int i = 0 ; i< H;i++) {
			for (int j = 0; j<N;j++) {
				for (int k= 0; k<M;k++) {
					if (dist[j][k][i] == -1) {
						System.out.println(-1);
						return;
					}
					answer = Math.max(answer, dist[j][k][i]);
				}
			}
		}
		
		System.out.println(answer);
	}
}