[알고리즘-PS] 백준 7576번 토마토 자바 문제풀이

[알고리즘-PS] 백준 7576번 토마토 자바 문제풀이

728x90

문제

해당 포스팅은 백준의 7576번 토마토 의 접근과 해결 방법을 설명한 글 입니다.

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

이번 문제는 BFS 를 이용해서 풀 수 있는 문제이다.

각각의 노드는 4방으로 상, 하, 좌, 우 로 연결된 그래프를 띄고 있는데, visited 라는 방문 체크 flag 가 필요 없는 문제이다.

하루에 1씩 썩어간다면 1 혹은 그 이상의 수가 존재한다면 이미 방문한 것으로 보고 넘어가도 되는 것이다.

정답 코드

public class Main { private static int[][] arr; private static ArrayList> graph = new ArrayList<>(); static int[] xPos = { -1, 1, 0, 0 }; static int[] yPos = { 0, 0, -1, 1 }; private static Queue queue = new LinkedList<>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String[] nm = br.readLine().split(" "); int n = Integer.parseInt(nm[0]); // x int m = Integer.parseInt(nm[1]); // y arr = new int[m][n]; for (int i = 0; i < arr.length; i++) { String[] inputs = br.readLine().split(" "); for (int j = 0; j < inputs.length; j++) { arr[i][j] = Integer.parseInt(inputs[j]); if(arr[i][j] == 1) { queue.add(new Position(j, i)); } } } decay(n, m); int answer = 0; for (int i = 0; i < arr.length; i++) { for(int value : arr[i]) { if(value == 0) { System.out.println(-1); return ; } answer = Math.max(answer, value); } } System.out.println(answer - 1); } private static void decay(int n, int m) { while(!queue.isEmpty()) { Position front = queue.remove(); for (int i = 0; i < 4; i++) { int xx = xPos[i] + front.x; int yy = yPos[i] + front.y; if(0 <= xx && xx < n && 0 <= yy & yy < m) { if(arr[yy][xx] == 0) { arr[yy][xx] = arr[front.y][front.x] + 1; queue.add(new Position(xx, yy)); } } } } } private static class Position { int x; int y; public Position(int x, int y) { this.x = x; this.y = y; } } }

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

728x90

from http://wonit.tistory.com/557 by ccl(S) rewrite - 2021-07-28 14:00:26