백준 7576번: 토마토

문제 설명

• 1에서부터 상하좌우로 움직일 수 있습니다.
• -1칸으로는 접근할 수 없습니다.
• 1에서부터 도달한 거리로 0의 값을 갱신합니다.
  • 여러 1에서 도달이 가능할 경우 가장 낮은 값으로 갱신합니다.
• 가장 큰 갱신된 값을 찾아야 합니다.

접근법

• BFS를 사용하는 문제입니다.
• 저는 시작점 1과 거리1을 구분하기 위해 시작점 1을 Integer.MIN_VALUE로 변경했습니다.
• while문 안에 queue의 size만큼 반복하는 while문을 하나 더 사용해서 동일한 Breadth를 표현했습니다.
  • 동일한 Breadth는 같은 cnt(시작점으로부터의 이동거리)를 가집니다.

시간초과

• 각 출발점에서 BFS를 실행하면 시간초과가 납니다.
  • 출발점의 개수만큼 BFS 실행
• 각 출발점을 모은 queue를 BFS에 넣고 BFS를 한번만 실행시켜줘야 합니다.
  • 1번만 BFS 실행
  • 진행과정을 print해보면 각 start지점에서 동시에 진행되는 걸 확인할 수 있습니다.

정답

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

public class Main {
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int[][] board = new int[N][M];
		Queue<int[]> q = new LinkedList<int[]>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine()," ");
			for (int j = 0; j < M; j++) {
				int val = Integer.parseInt(st.nextToken());
				if(val == 1) {
					board[i][j] = Integer.MIN_VALUE; // 시작점 1과, 1일차 1을 구분하기 위해
					int[] temp = {i,j};
					q.add(temp);
				}else {			
					board[i][j] = val;
				}

			}
		}
		
        // 정답코드: BFS를 실행해야 하는 좌표를 q에 넣어 한번에 BFS에 넣음
		BFS(N,M,board,q);
        
        // 시간초과코드: BFS의 좌표 하나하나를 BFS에 넣음
		// while(!lst.isEmpty()) {
		//  	BFS(lst.poll(),N,M,board);
		// }
		
		int answer = 0;
		Here: for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(board[i][j] == 0) {
					answer = -1;
					break Here;
				}
				answer = Math.max(answer, board[i][j]);
			}
		}
		System.out.println(answer);
		
	}
	
	public static void BFS(int N, int M , int[][] board,Queue<int[]> q) {
		// 시간초과 코드
		// Queue<int[]> q = new LinkedList<int[]>();
		// q.offer(start);

		int cnt = 0;
		while(! q.isEmpty()) {
        	// 진행과정 확인코드 -> 주석을 풀고 눈으로 보는걸 추천드립니다.
			// for (int i = 0; i < board.length; i++) {
			// 	  System.out.println(Arrays.toString(board[i]));
			// }
			// System.out.println("=========");        
			int size = q.size();
			cnt++;
			while(--size>=0) {				
				int[] temp = q.poll();
				int x = temp[0];
				int y = temp[1];
				for (int i = 0; i < 4; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if(0<= nx && nx < N && 0<= ny && ny < M && (board[nx][ny] == 0 || board[nx][ny] > cnt)) { // 정답코드에서는 board[nx][ny] > cnt는 필요없습니다.
						board[nx][ny] = cnt;
						int[] temp2 = {nx,ny};
						q.offer(temp2);
					}
				}
			}
		}
        
	}
    
}

기타

배운점

• queue에 여러 좌표값을 넣어두고 BFS를 돌리면, 각 좌표에서의 BFS가 동시에 실행된다.