백준 7569번 - 토마토

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

7569번: 토마토

 

각 격자모양 안에 토마토가 들어있는데, 토마토가 익은 경우 즉 값이 1인 경우에는 하루마다 주위의 토마토를 모두

익게 만든다. 또한 -1은 토마토가 없는 상태이다. 각 층의 상자안에 들어있는 토마토가 모두 익을때까지 소요되는 일수를구하는 문제로 해당 문제는 bfs(Breadth-First Search) 알고리즘을 사용하여 푸는 문제이다.

 

기존 토마토 문제는 높이를 고려하지 않아도 되었지만 해당 문제는 높이까지 고려해줘야 하는 문제로 

기존문제의 응용버젼이라고 생각하면 된다. 앞의 토마토문제의 해법을 보게 되면 해당문제는 쉽게풀린다.

토마토문제_7576

 

해당문제를 해결하는 알고리즘은 아래와 같다.

 

1. 미로의 map(토마토의 유무를 표기해주는 벡터) 과 visit(해당 위치를 방문했는지 체크해주는 벡터) 을 만들어 탐색을 준비한다.

 

2. Node 객체를 준비하여 해당 객체의 높이,행,열 위치 정보와 현재 몇일째인지 정보를 저장한다.

 

3. Queue 를 만들어준다 해당 큐에 들어갈 수 있는 객체는 Node 객체이다.

 

4. map 을 초기화해주면서 만약 1이 들어가는 경우에는 queue 에 해당 높이, 행,열 위치정보와 날짜 0 을 넣어서 enqueue 해준다.

 

5. queue 에서 Node 객체를 꺼내어 상하좌우 윗층 아래층을 탐색해주는데 탐색조건에 부합하게 되면 (해당 map 행/열의 토마토값이 0 인경우) 새로운 높이 위치, 새로운 행 위치, 새로운 열 위치 , 기존 Node 날짜정보 + 1 인 Node 를 생성하여 enqueue  작업을 수행한다. 또한 visit 행렬에는 해당 높이, 해당 행,열 위치값에 기존 Node 날짜정보 + 1 을 저장해준다.

 

6. queue 가 비워진 상태가 되면 map 을 순회하면서 아직 익지 않은 토마토가 하나라도 있으면 -1을 리턴해주고 그렇지 않다면

가장 큰 Node 날짜정보를 리턴시킨다.

 

 

기존문제와 다른점은 빨간색으로 표시된 부분이 익은 토마토가 있다고 가정하면 1일뒤에는 아래와 같이

6방향 인접해 있는 토마토들이 모두 익게된다.

 

 

 

JAVA 풀이

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

public class Main
{   
    static int N,M,H;
    static int[][][] map;
    static int[][][] visit;
    static int[] dh = {1,-1,0,0,0,0};
    static int[] dr = {0,0,0,0,-1,1};
    static int[] dc = {0,0,1,-1,0,0};
    static Queue<Node> queue = new ArrayDeque<>(); 
    
    static class Node {
        int h,r,c,day;
        
        public Node(int h,int r, int c, int day) {
            this.h = h;
            this.r = r;
            this.c = c;
            this.day = day;
        }
    }
    
	public static void main(String[] args) throws Exception {
	    
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
	    String[] inputs = br.readLine().split(" ");
	    N = Integer.parseInt(inputs[1]);
	    M = Integer.parseInt(inputs[0]);
	    H = Integer.parseInt(inputs[2]);
	    
	    map = new int[H][N][M];
	    visit = new int[H][N][M];
	    
	    for (int i = 0; i < H; i++) {
	        for (int j = 0; j < N; j++) {
	            String[] hrc = br.readLine().split(" ");
	            for (int k = 0; k < M; k++) {
	                int num = Integer.parseInt(hrc[k]);
	                map[i][j][k] = num;
	                if (num == 1) queue.offer(new Node(i,j,k,0));
	            }
	        }
	    }
	    
	    int result = bfs();
	    
	    bw.write(result + "");
	    bw.close();
	    br.close();
	}
	
	static int bfs() {
	   
	    while(!queue.isEmpty()) {
	        Node nd = queue.poll();
	        
	        for (int i = 0; i < 6; i++) {
	            
	            int nh = nd.h + dh[i];
	            int nr = nd.r + dr[i];
	            int nc = nd.c + dc[i];
	            
	            if (nh < 0 || nr < 0 || nc < 0 || nh >= H || nr >= N || nc >= M) continue;
	            
	            if (map[nh][nr][nc] == 0 && visit[nh][nr][nc] == 0) {
	                queue.offer(new Node(nh,nr,nc,nd.day + 1));
	                map[nh][nr][nc] = 1;
	                visit[nh][nr][nc] = nd.day + 1;
	            }
	        }
	    }
	    
	    int maxDay = 0;
	    int page = N*M;
	    
	    for (int i = 0; i < H*N*M; i++) {
	        int indexH = i/page;
	        int indexI = i%page;
	        int indexValue = map[indexH][indexI/M][indexI%M];
	        if (indexValue == 0) return -1;
	        
	        int wantDays = visit[indexH][indexI/M][indexI%M];
	        maxDay = maxDay > wantDays ? maxDay : wantDays;
	    }
	    
	    return maxDay;
	}
	
}

 

 

C++ 풀이

#include <iostream>
#include <queue>

using namespace std;

typedef struct {
    int h,r,c,day;
} node;

int map[101][101][101];
int visit[101][101][101];
queue<node> q;
int H,N,M;
int dh[6] = {1,-1,0,0,0,0};
int dr[6] = {0,0,1,-1,0,0};
int dc[6] = {0,0,0,0,1,-1};
int bfs();

int main()
{
    scanf("%d %d %d",&M,&N,&H);
    
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < M; k++) {
                int num;
                scanf("%d",&num);

                if (num == 1) {
                    node nd = {i,j,k,0}; 
                    q.push(nd);
                }
                map[i][j][k] = num;
            }
        }
    }

    int result = bfs();

    printf("%d",result);

    return 0;
}

int bfs() {
    
    while(!q.empty()) {
        node nd = q.front();
        q.pop();

        for (int i = 0; i < 6; i++) {
            int nh = nd.h + dh[i];
            int nr = nd.r + dr[i];
            int nc = nd.c + dc[i];

            if (nh < 0 || nr < 0 || nc < 0 || nh >= H || nr >= N || nc >= M) continue;

            if (map[nh][nr][nc] == 0 && visit[nh][nr][nc] == 0) {
                node nds = {nh,nr,nc,nd.day + 1};
                q.push(nds);
                map[nh][nr][nc] = 1;
                visit[nh][nr][nc] = nd.day + 1;
            }
        }
    }

    int max_day = 0;
    int index = M*N;

    for (int i = 0; i < H*N*M; i++) {
        int page_index = i / index;
        int rest_index = i % index;
        
        if(map[page_index][rest_index/M][rest_index%M] == 0) return -1;

        int visit_value = visit[page_index][rest_index/M][rest_index%M];

        max_day = max_day > visit_value ? max_day : visit_value;

    }

    return max_day;
}