백준 7576번 - 토마토

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

7576번: 토마토

 

각 격자모양 안에 토마토가 들어있는데,

 

토마토가 익은 경우 즉 값이 1인 경우에는 하루마다 주위의 토마토를 모두익게 만든다.

 

또한 -1은 토마토가 없는 상태이다.

 

상자내의 토마토가 모두 익을때까지 소요되는 일수를 구하는 문제로

 

해당 문제는 BFS(Breadth-First Search) 알고리즘을 사용하여 푸는 문제이다.

 

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

 

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 날짜정보를 리턴시킨다.

 

해당 로직을 단계별로 도식화해보면 아래와 같다.

왼쪽 행렬이 map 행렬이고 오른쪽 행렬이 visit 행렬이다.

 

 

 

 

1. JAVA

 

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

public class Main
{   
    static int N,M;
    static int[][] map;
    static int[][] visit;
    static int[] dr = {0,0,-1,1};
    static int[] dc = {1,-1,0,0};
    static Queue<Node> queue = new ArrayDeque<>(); 
    
    static class Node {
        int r,c,day;
        
        public Node(int r, int c, int day) {
            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]);
	    
	    map = new int[N][M];
	    visit = new int[N][M];
	    
	    for (int i = 0; i < N; i++) {
	        String[] rc = br.readLine().split(" ");
	        for (int j = 0; j < M; j++) {
	            int num = Integer.parseInt(rc[j]);
	            if (num == 1) queue.offer(new Node(i,j,0));

	            map[i][j] = num;
	        }
	    }
	    
	    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 < 4; i++) {
	            int nr = nd.r + dr[i];
	            int nc = nd.c + dc[i];
	            
	            if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
	            
	            if (map[nr][nc] == 0) {
	                map[nr][nc] = 1;
	                queue.offer(new Node(nr,nc,nd.day + 1));
	                visit[nr][nc] = nd.day + 1;
	            }
	        } 
	    }//while

	    int maxDay = 0;
	    
	    for (int i = 0; i < N; i++) {
	        for (int j = 0; j < M; j++) {
	            if (map[i][j] == 0) return -1;
	            else if (map[i][j] != -1) {
	                maxDay = visit[i][j] > maxDay ? visit[i][j] : maxDay;
	            }
	        }
	    }
	    
	    return maxDay;
	}	
}

 

 

2. C++

#include <iostream>
#include <queue>

using namespace std;

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

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

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

            if (num == 1) {
                q.push({i,j,0});
            }
            map[i][j] = 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 < 4; i++) {
            int nr = nd.r + dr[i];
            int nc = nd.c + dc[i];

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

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

    int max_day = 0;

    for (int i = 0; i < N*M; i++) {
        if (map[i/M][i%M] == 0) return -1;
        else max_day = visit[i/M][i%M] > max_day ? visit[i/M][i%M] : max_day;
    }

    return max_day;
}