백준[7576 , 7569] 토마토 (JAVA)

이번에 풀어볼 문제는 BFS 문제중 기출 문제라고 볼 수 있는 토마토 문제를 풀어보겠다.

 

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

7576번: 토마토

 

첫번째 토마토 문제이다.

 

기존의 탐색문제들과 조금 다른 점은 탐색을 시작해야 하는 정점이 여러곳이라는 부분이다.

 

그동안 BFS문제를 풀 때 접근 방식은 시작정점을 큐에 넣고 꺼내서 해당 정점에 대한 탐색을 이어나가는 식으로

탐색을 진행했었고 이 문제 역시 같은 방식을 따르면 된다.

 

다만 시작 정점이 여러개가 될수 있으므로 순차적으로 시작정점 모두를 큐에 넣어놓고 탐색을 시작하면 된다.

 

예를 들어 시작 정점이 1,2,3 이렇게 3개가 있다면 1,2,3 모두를 큐에 넣고 시작하는것이다.

1에서 탐색이 가능한 다른 정점 탐색후 큐에 삽입 후 다음 정점인 2에 대해 탐색을 진행하고 그 다음 정점인 3에 대해

탐색을 진행하는식으로 이루어진다. 각 정점들에 대한 방문처리가 이루어진다면 최단거리가 보장되기 때문에

실제 탐색 자체는 순차적으로 이루어지지만 최단거리 혹은 비용은 보장이되는 탐색인것이다.

 

문제에서 각 토마토는 현재 토마토의 상하좌우 토마토만 익을수 있다는게 조건이므로

 

dx, dy 배열을 만들어주고 BFS 탐색을 위한 큐와 변수들에 대한 자원을 선언해준다.

 

	static int n,m,front,rear,size;
	static Point[] queue;
	static int[][] metrix;
	
	static int[] dx = { 0 , 1 , 0 , -1};
	static int[] dy = { 1 , 0 , -1 , 0};

 

 

다음은 큐와 방문처리, 비용을 저장할 배열에 대해 동적으로 메모리를 할당할 메소드를 만들어준다.

 

	static void init() {
		size = n*m;
		queue = new Point[size];
		metrix = new int[m][n];
	}

 

다음은 BFS 메소드이다 해당 메소드에 대해서는 그간 다른 문제에서 접근한 방식과 동일한 방식의 메소드이므로

자세한 설명은 생략하도록 하겠다.

 

조금 차이가 있다면 인자로 시작정점들에 대한 배열을 받아 큐에 삽입하는 과정이 추가된다는 점이다.

 

	static void bfs(Point[] start, int len) {
		for(int i = 0; i < len; i++) {
			queue[rear++] = start[i];
		}
		while(queue[front] != null) {
			Point node = queue[front];
			queue[front++] = null;
			front%=size;
			for(int i = 0; i < 4; i++) {
				int x = node.x + dx[i];
				int y = node.y + dy[i];
				if(x >= 0 && y >= 0 && x < m && y < n && metrix[x][y] == 0) {
					queue[rear++] = new Point(x,y);
					metrix[x][y] = metrix[node.x][node.y] + 1;
					rear%=size;
				}
			}
		}
	}

 

다음은 이제 탐색이 끝난 후 현재 최대비용을 구하는것이 답이므로 

최대 비용을 구하기 위한 메소드를 하나 만들어준다.

 

문제에서 토마토가 모두 익지못하는 경우는 -1을 출력하라고 했으므로 탐색이 이루어지지 않은 정점이 있다면

-1을 반환해주고

모든 정점을 거쳐 최대비용을 갖는 값에 대해 리턴해주도록 한다.

이때 방문처리를 겸하는 배열이라 시작정점에 대해 1을 넣어주고 시작했으므로 

리턴시 -1의 보정처리를 해준다.

 

	static int chk() {
		int max = 0;
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < n; j++) {
				if(metrix[i][j] == 0) {
					return -1;
				}
				max = Math.max(max, metrix[i][j]);
			}
		}
		return max - 1; // 시작이 1이였으므로 -1로 보정처리... 구하고자 하는것은 일수이다
	}

 

 

코드를 실행시켜 본다면

 

 

입력값에 대해 정확한 답을 내는것을 확인 할 수 있다.

 

아래는 코드의 전문이다.

 

package boj2;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj7576 {
	
	/*
	 * BFS
	 * 제출 完
	 */
	
	static int n,m,front,rear,size;
	static Point[] queue;
	static int[][] metrix;
	
	static int[] dx = { 0 , 1 , 0 , -1};
	static int[] dy = { 1 , 0 , -1 , 0};
	
	static void init() {
		size = n*m;
		queue = new Point[size];
		metrix = new int[m][n];
	}
	
	static void bfs(Point[] start, int len) {
		for(int i = 0; i < len; i++) {
			queue[rear++] = start[i];
		}
		while(queue[front] != null) {
			Point node = queue[front];
			queue[front++] = null;
			front%=size;
			for(int i = 0; i < 4; i++) {
				int x = node.x + dx[i];
				int y = node.y + dy[i];
				if(x >= 0 && y >= 0 && x < m && y < n && metrix[x][y] == 0) {
					queue[rear++] = new Point(x,y);
					metrix[x][y] = metrix[node.x][node.y] + 1;
					rear%=size;
				}
			}
		}
	}
	
	static int chk() {
		int max = 0;
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < n; j++) {
				if(metrix[i][j] == 0) {
					return -1;
				}
				max = Math.max(max, metrix[i][j]);
			}
		}
		return max - 1; // 시작이 1이였으므로 -1로 보정처리... 구하고자 하는것은 일수이다
	}
	
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		init();
		
		boolean flag = false;
		int cnt = 0;
		Point[] start = new Point[size];
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j = 0; j < n; j++) {
				metrix[i][j] = Integer.parseInt(st.nextToken());
				if(metrix[i][j] == 0) {
					flag = true;
				} else if(metrix[i][j] == 1) {
					start[cnt++] = new Point(i,j);
				}
			}
		}
		
		in.close();
		
		if(flag) {
			bfs(start,cnt);
			System.out.print(chk());
		}else {
			System.out.print(0);
		}
	}

}

 

 

다음은 역시 같은 문제이나 이번엔 2차원이 아닌 3차원으로 확장하는 문제이다.

 

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

7569번: 토마토

 

위에서 다루었던 문제와 시작정점이 여러개라는 부분은 같지만 이번엔 탐색방향이 가로세로에서 상하까지

추가해서 진행된다는 점이 조금 특이하다.

 

그말은 탐색을 진행할 좌표가 x축, y축 두가지에서 z축까지 확장이 된단 소리이고

 

그동안 사용해왔던 java.awt 패키지의 Point 클래스가 아닌 별도의 클래스를 정의해 객체를 사용해야한다.

 

그러나 현재 PS 문제풀이중이므로 별도의 클래스 파일을 만들어 사용하기보단

현재 클래스 내에서 멤버변수를 선언하고 메소드와 현재클래스의 객체를 활용해 풀어보도록 하겠다.

 

우선 x,y,z 좌표에 해당하는 값에 대해 저장할 멤버변수와 객체가 생성되면서 멤버변수에 값을 저장할 생성자를

만들어주도록 하겠다.

 

	int x,y,z;
	
	Boj7569(int x, int y, int z){
		this.x = x;
		this.y = y;
		this.z = z;
	}

 

이번 문제는 상하좌우 위칸, 아래칸 총 6방향으로 탐색이 이루어지므로 dx,dy,dx 배열을 만들어준다.

 

		int[] dx = { 0 , 1 , 0 , -1 , 0 , 0 };
		int[] dy = { 1 , 0 , -1 , 0 , 0 , 0 };
		int[] dz = { 0 , 0 , 0 , 0 , 1 , -1 };

 

그리고 이번 문제는 특별히 메소드로 나누지 않고 그냥 main 내부에서 반복문 만으로 해결해보도록 하겠다.

 

일단 현재 클래스의 멤버변수로 x,y,z 값을 저장하기로 했으므로 시작정점을 저장할 배열, 그리고 큐를 선언해준다.

그리고 실제 탐색에 대해 방문처리겸 데이터를 저장할 3차원 배열도 만들어준다.

 

		int[][][] metrix = new int[h][m][n];
		Boj7569[] queue = new Boj7569[size];
		Boj7569[] start = new Boj7569[size];

 

 

다음은 순차적으로 입력을 받으며 1인 경우 객체를 생성해 시작정점배열에 저장해준다.

 

		for(int i = 0; i < h; i++) {
			for(int j = 0; j < m; j++) {
				st = new StringTokenizer(in.readLine()," ");
				for(int k = 0; k < n; k++) {
					metrix[i][j][k] = Integer.parseInt(st.nextToken());
					if(metrix[i][j][k] == 1) {
						start[cnt++] = new Boj7569(i,j,k);
					}else if(metrix[i][j][k] == 0) {
						flag = true;
					}
				}
			}
		}

 

 

이후 시작정점 모두를 큐에 삽입해준다.

 

		for(int i = 0; i < cnt; i++) {
			queue[rear++] = start[i];
		}

 

이제 정점을 하나씩 꺼내 6회 순회하며 탐색을 진행하는 반복문을 작성해준다.

 

		while(queue[front] != null) {
			Boj7569 node = queue[front];
			queue[front++] = null;
			front%=size;
			for(int i = 0; i < 6; i++) {
				int x = node.x + dx[i];
				int y = node.y + dy[i];
				int z = node.z + dz[i];
				
				if(x >= 0 && y >= 0 && z >= 0 &&
						x < h && y < m && z < n &&
						metrix[x][y][z] == 0) {
					queue[rear++] = new Boj7569(x,y,z);
					rear%=size;
					metrix[x][y][z] = metrix[node.x][node.y][node.z] + 1;
				}
			}
		}

 

이후 역시 최대 비용을 찾거나 예외 상황에 대해 처리해주면 된다.

 

		if(flag) {
			
			for(int i = 0; i < h; i++) {
				for(int j = 0; j < m; j++) {
					for(int k = 0; k < n; k++) {
						if(metrix[i][j][k] == 0) {
							flag = false;
						}
						max = Math.max(max, metrix[i][j][k]);
					}
				}
			}
			
			max = (flag) ? max : 0;
			
			System.out.print(--max);
		}else {
			System.out.print(0);
		}

 

 

예제 입력을 해보면 

 

 

예제에 대한 답을 잘 출력하는것을 볼 수 있다.

 

아래는 코드의 전문이다.

 

package boj2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj7569 {
	
	/*
	 * 제출 完
	 */
	
	int x,y,z;
	
	Boj7569(int x, int y, int z){
		this.x = x;
		this.y = y;
		this.z = z;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());
		
		int size = n*m*h;
		int front = 0;
		int rear = 0;
		int cnt = 0;
		int max = 0;
		boolean flag = false;
		
		int[][][] metrix = new int[h][m][n];
		Boj7569[] queue = new Boj7569[size];
		Boj7569[] start = new Boj7569[size];
		
		int[] dx = { 0 , 1 , 0 , -1 , 0 , 0 };
		int[] dy = { 1 , 0 , -1 , 0 , 0 , 0 };
		int[] dz = { 0 , 0 , 0 , 0 , 1 , -1 };
		
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < m; j++) {
				st = new StringTokenizer(in.readLine()," ");
				for(int k = 0; k < n; k++) {
					metrix[i][j][k] = Integer.parseInt(st.nextToken());
					if(metrix[i][j][k] == 1) {
						start[cnt++] = new Boj7569(i,j,k);
					}else if(metrix[i][j][k] == 0) {
						flag = true;
					}
				}
			}
		}
		
		in.close();
		
		for(int i = 0; i < cnt; i++) {
			queue[rear++] = start[i];
		}
		
		while(queue[front] != null) {
			Boj7569 node = queue[front];
			queue[front++] = null;
			front%=size;
			for(int i = 0; i < 6; i++) {
				int x = node.x + dx[i];
				int y = node.y + dy[i];
				int z = node.z + dz[i];
				
				if(x >= 0 && y >= 0 && z >= 0 &&
						x < h && y < m && z < n &&
						metrix[x][y][z] == 0) {
					queue[rear++] = new Boj7569(x,y,z);
					rear%=size;
					metrix[x][y][z] = metrix[node.x][node.y][node.z] + 1;
				}
			}
		}
		
		if(flag) {
			
			for(int i = 0; i < h; i++) {
				for(int j = 0; j < m; j++) {
					for(int k = 0; k < n; k++) {
						if(metrix[i][j][k] == 0) {
							flag = false;
						}
						max = Math.max(max, metrix[i][j][k]);
					}
				}
			}
			
			max = (flag) ? max : 0;
			
			System.out.print(--max);
		}else {
			System.out.print(0);
		}
		
	}

}