![[백준,BOJ 7576] 토마토(JAVA 구현, 추가풀이)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FrvOzh%2FbtqzJdenpTM%2FipgdJFP6ZosCWT6tmKVRCK%2Fimg.png)
반응형
-내 생각
알고리즘 문제를 계속해서 풀다 보니까 이제 언제 DFS를 쓰고 언제 BFS를 써야 하는지 감이 좀 잡히는 듯하다. 이번 문제의 경우에는 토마토가 인접한 토마토를 1일이 지날 때마다 익게 한다는 것이 포인트라고 생각했다. 즉 초기에 주어지는 익은 토마토를 기준으로 인접한 토마토를 모두 익게 만들면 되는 것인데, 인접한 노드를 모두 탐색하는 것은 BFS이므로 BFS를 사용하면 될 것 같다고 생각했다. 하지만 이번 문제 역시 막힌 부분이 있었는데, 입력으로 익은 토마토가 1개 주어질 경우는 구현이 됐지만, 익은 토마토가 2개 이상 주어지면 답이 이상해졌다. 역시 다른 블로그 분들의 글을 보고 힌트를 얻을 수 있었다.
-해법
위에서 언급한 문제점이 발생된 이유는 초기 인자를 넘겨줄 때 모든 칸을 탐색하면서 익은 토마토를 발견하면 BFS를 실행했다는 점에 있었다. 그 말인즉슨, 첫 번째 칸에 익은 토마토가 있고 마지막 칸에 익은 토마토가 있으면 첫 번째 칸을 기준으로 BFS를 실행해버리기 때문에 마지막 토마토는 무시돼버리는 것이었다. 이를 해결하기 위해서는 익은 토마토를 동시에 고려해주어야 한다. 즉 익은 토마토의 좌표를 애초에 큐에 모두 삽입해버려 첫 번째 익은 토마토의 인접한 토마토를 익게 하고 마지막 번째에 익은 토마토의 인접한 토마토를 익게 하고.... 같은 식으로 반복하면 동시에 진행하는 것과 같은 효과를 낼 수 있다. 자세한 내용은 코드를 보며 이해해 보자.
import java.util.*;
class xy{ //xy좌표 저장 클래스
int x;
int y;
public xy(int x,int y) {
this.x= x;
this.y =y;
}
}
public class Main {
static int node[][]; // 토마토가 저장 될 2차원 배열
static int check[][]; // 해당 토마토가 익는 일수가 저장 될 배열 겸 방문 배열
static int cnt=1;
static int n,m;
public static void bfs(Queue<xy> q) { //BFS메소드
//익은 토마토의 좌표가 큐에 저장되어 전달된다.
while(!q.isEmpty()) { // 이제 큐가 공백이 될 때 까지 반복한다.
int x = q.peek().x; // 큐에 저장되어 있는 객체에서 x,y좌표를 저장
int y = q.peek().y;
q.poll(); // 큐에서 peek후 저장한 것이기 때문에 별도이 poll()수행으로 해당 객체 소멸
//아래의 조건문은 DFS게시글에서 사용한 조건문과 동일
if(y<node[x].length-1&& check[x][y+1]==0) {
check[x][y+1]=check[x][y]+1; // 현재 점이 가지고 있는 경로값을 인접한 점의 방문배열에 저장
q.offer(new xy(x,y+1)); // 인접한 점을 큐에 넣어준다.
//아래는 모두 이와 동일
}
if(x<node.length-1&&check[x+1][y]==0) {
check[x+1][y]=check[x][y]+1;
q.offer(new xy(x+1,y));
} if(x>0&& check[x-1][y]==0) {
check[x-1][y]=check[x][y]+1;
q.offer(new xy(x-1,y));
}
if(y>0&& check[x][y-1]==0) {
check[x][y-1]=check[x][y]+1;
q.offer(new xy(x,y-1));
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Queue<xy> queue = new LinkedList<>(); // 익은 토마토의 좌표가 저장 될 큐
m = sc.nextInt();
n = sc.nextInt();
node = new int [n][m];
check = new int[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
node[i][j] = sc.nextInt();
}
}
//------------------------입력부 끝---------------
for(int i=0;i<n;i++) { // 토마토를 모두 탐색해 익은 토마토를 큐에 저장
for(int j=0;j<m;j++) {
if(node[i][j]==1 && check[i][j]==0) {
queue.add(new xy(i,j));
check[i][j] =1;
}
if(node[i][j]== -1) // 상한 토마토는 익을 수 없기 때문에 check배열에 역시 -1로 저장
check[i][j]=-1;
}
}
bfs(queue); // BFS 메소드에 큐 전달
int max = Integer.MIN_VALUE;
for(int i=0;i<n;i++) { // 완성된 check배열을 탐색
for(int j=0;j<m;j++) {
if(check[i][j]==0) { //check배열에 0이 한개라도 존재하면 모두 익을 수 없는 경우이다.
System.out.println("-1");
return;
}
if(check[i][j]>max) { //시작일수가 1이므로 max값을 찾아
max = check[i][j];
}
}
}
System.out.println(max -1); //-1을 해주면 모두 익는데 소모되는 일수가 나온다.
}
}
이 문제 역시 이전에 풀이와 비슷한 방식으로 풀이했지만, 코드 자체는 좀 더 간결해진 느낌이다.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Dot{ // 익은 토마토 좌표 클래스
int x;
int y;
public Dot(int x, int y) {
super();
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
class Main {
static Queue<Dot> q = new LinkedList<>(); // 익은 토마토를 모두 저장한 뒤 BFS 수행을 위한 큐
static int dx[] = {1,-1,0,0};
static int dy[] = {0,0,1,-1};
// BFS 메소드
static void bfs(int[][] a, int[][] check) {
while(!q.isEmpty()) {
Dot d_p = q.poll();
int x = d_p.getX();
int y = d_p.getY();
for(int i=0;i<4;i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx>=a.length || nx<0 || ny>=a[nx].length || ny < 0) continue;
// 썩은 토마토는 패스
if(a[nx][ny] == -1) continue;
// 익지 않은 토마토 중 방문하지 않은 토마토인 경우
if( check[nx][ny] == Integer.MAX_VALUE ){
// 최소 일 수를 저장
check[nx][ny] = Math.min(check[x][y]+1,check[nx][ny]);
// 해당 좌표부터 다시 BFS 수행을 위해 큐에 삽입
q.offer(new Dot(nx,ny));
}
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int max = 0;
int map[][] = new int[m][n]; // 토마토 저장 맵
int check[][] = new int[m][n]; // 토마토 방문 여부 체크 배열
// 토마토 좌표 정보 입력
for(int i =0;i<map.length;i++) {
for(int j=0;j<map[i].length;j++) {
map[i][j] = in.nextInt();
}
}
// 최소 일 수를 구하기 위해 check 배열을 모두 최댓값으로 채워준다.
for(int i =0;i<check.length;i++) {
Arrays.fill(check[i], Integer.MAX_VALUE);
}
Dot d;
for(int i =0;i<map.length;i++) {
for(int j=0;j<map[i].length;j++) {
// 익은 토마토이면서 방문한 적 없는 토마토는
if(map[i][j] == 1 && check[i][j] == Integer.MAX_VALUE) {
d = new Dot(i,j); // 해당 좌표 객체 생성
q.offer(d); // 큐에 삽입
check[i][j] = 1; // 방문 표시 및 시작일 수인 1 저장
}else if (map[i][j] == -1) // 동시에 썩은 토마토는 -1로 check 배열에 표시
check[i][j] = -1;
}
}
// 전역으로 선언한 큐를 활용해 BFS 수행
bfs(map,check);
// check에 저장된 일 수의 최댓값을 찾는다.
for(int i =0;i<check.length;i++) {
for(int j=0;j<check[i].length;j++) {
if(check[i][j] > max) {
max = check[i][j];
}
}
}
// 최댓값이 1인 경우는 모두 익어있는 상태이라는 뜻.
if(max == 1) System.out.println(0);
// 최댓값이 초기화했던 최대 정수값이라면 모두 익을 수 없는 상태라는 뜻.
else if(max == Integer.MAX_VALUE) System.out.println(-1);
// 그 외에는 최댓값에서 -1을 수행하면 모든 토마토가 익는 최소 일수가 된다.
else System.out.println(max - 1);
in.close();
}
}반응형