[백준/java] 7576번 : 토마토 - BFS

7576번 : 토마토

 

728x90

 

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

7576번: 토마토

 

7576번 : 토마토

 

※ 문제 풀이방식

BFS가 응용된 부분 위주로 설명 드리겠습니다

 

반응형

 

(1) 우선 dy, dx 배열의 값은 두개의 값들을 함께보면 (1, 0), (0, 1), (-1, 0), (0, -1) 이 순으로 되어있습니다.

 --> 이것이 의미하는 것은 북 동 남 서 방향으로 방향을 설정하는 것입니다.

(2) Node 클래스에 기존에 풀이했던 그림, 섬의 개수, 안전 영역같은 문제들과는 달리 x, y, 그리고 step 변수가 있는데, 이것은 BFS로 탐색하며 이동하면서( 날짜가 지날때마다 )추가되는 일수의 카운트 입니다.

(3) 원래는 cur.step++;으로 해서 q.add(new Node(y,x,cur.step));을 넣어서 탐색했었는데,

    그렇게 실행하면 테스트케이스 3번이 오류가 나더라구요.

(4) 방향 순회하는 for문 안에 step이라는 변수를 새로 만들어서 큐에 다시 넣어주니 정상적으로 값이 나옵니다. 아무래도 q가 static  객체로 선언되어서 그 안에 들어가는 Node들까지 영향을 받는 것 같습니다.

 

package bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Tomato1 {
	static int[][] map;
	static boolean[][] visit;
	static int[] dy = {1, 0, -1, 0};
	static int[] dx = {0, 1, 0, -1};
	static int N, M;
	static Queue<Node> q = new LinkedList<Node>();
	static class Node {
		int y, x, step;
		public Node(int y, int x, int step) {
			this.x = x;
			this.y = y;
			this.step = step;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		M = stoi(st.nextToken()); N = stoi(st.nextToken());
		map = new int[N][M]; visit = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				map[i][j] = stoi(st.nextToken());
				if(map[i][j] == 1) {
					q.add(new Node(i, j, 0));
				}
			}
		}
		
		int day = bfs();
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(map[i][j] == 0) {
					System.out.println(-1);
					return;
				}
			}
		}
		
		System.out.println(day);
	}
	
	public static int bfs() {
		int day = 0;
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			visit[cur.y][cur.x] = true;
			
			for (int dir = 0; dir < 4; dir++) {
				int ny = cur.y + dy[dir];
				int nx = cur.x + dx[dir];
				
				if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
				if(map[ny][nx] == -1 || map[ny][nx] == 1 || visit[ny][nx]) continue;
				
				visit[ny][nx] = true;
				
				int step = cur.step + 1; 
				map[ny][nx] = 1;
				q.add(new Node(ny, nx, step));
			}
			
			day = cur.step;
		}
		
		return day;
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}