[백준] 7576 토마토 - BFS

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

7576번: 토마토

 

 

문제풀이

BFS 문제입니다.

문제 조건에 

1. 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 

라는 조건이 있습니다.

일반적으로 M이 행(세로) 이고 N이 열(가로) 인 경우가 많지만, 이 문제 같은경우 반대로 되어있습니다.이때, 단순하게 N을 먼저 입력받고 똑같이 진행하면 y = x 대칭으로 바뀌게 되어 M이 가로 칸의 수이지만 세로로 변하고, N이 세로 칸의 수이지만 가로로 변하기에 일반 문제랑 똑같이 진행하면 됩니다.

또한 M, N 이 1000 이기에 최대 1000 * 1000 = 1,000,000(백만) 개의 수를 입력받는데 이떄 시간초과가 날 수 있습니다.

일반적으로 1억개의 연산이 진행되어야 1초 초과인데, 입출력같은경우 시간이 더 오래걸리기에 이런 많은 입력을 받을떄는  BufferedReader를 활용하여 진행해야 시간초과가 나지 않습니다.

 

2. 문제에서 익은 토마토는 1개가 아니라 여러개가 될 수 있다.

저 같은경우 이 조건을 늦게봐서 1개인줄알고 코드를 풀었다가 예제 3번의 예시를 보고 다시 재수정했습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	
	public static int M, N, result=0;
	public static int[][] map;
	public static boolean[][] visited;
	public static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	
    	map = new int[M][N];
    	visited = new boolean[M][N];
    	int startx = 0, starty = 0;
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    			if(map[i][j] == 1) {
    				q.offer(new Node(i,j, 0));
    				startx = i;
    				starty = j;
    			}
    		}
    	}
    
    	BFS();
    	
    	for(int i=0;i<M;i++) {
    		for(int j=0;j<N;j++) {
    			if(map[i][j] == 0) {
    				System.out.println("-1");
    				return ;
    			}
    		}
    	}
    	System.out.println(result);
    	
    	
    }
    public static void BFS() {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	
//    	visited[startx][starty] = true;
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int y = temp.y;
    		int time = temp.time;
    		result = time;
        	visited[x][y] = true;
    		for(int dir=0;dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			
    			if(nx < 0 || nx >= M || ny < 0 || ny >= N ) continue;
    			if(visited[nx][ny] == true) continue;
    			if(map[nx][ny] == -1 || map[nx][ny] == 1) continue;
    			
    			q.offer(new Node(nx, ny, time + 1));
    			visited[nx][ny] = true;
    			map[nx][ny] = 1;
    		}
    	}
    }
    
    
}
class Node{
	int x;
	int y;
	int time;
	public Node(int x, int y, int time) {
		this.x = x;
		this.y = y;
		this.time = time;
	}
}