[백준 BOJ] 7576번 토마토 (Java)

문제 설명

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

 

 

접근 방법 - 너비 우선 탐색(BFS) 응용문제

백준의 7576번 문제는 너비 우선 탐색(BFS) 알고리즘을 활용하여 해결해야 하는 문제이다.

해당 문제는, 토마토의 정보가 입력으로 주어지고 특정 규칙에 따라 토마토가 익을 때 모든 토마토가 익는 최소 일수를 구하여 출력해야 하는 문제이다.

구체적인 문제 설명은 아래에도 기재해 놓으나, 보다 자세한 내용은 문제의 본문을 참고하길 바란다.

• 익지 않은 토마토는 0으로, 이미 익은 토마토는 1로 입력받는다. 토마토가 없는 공간은 -1로 입력받는다.
• 보관 후 하루가 지나면, 익은 토마토(1)로부터 인접한 익지 않은 토마토들(0)은 이에 영향을 받아 익게 된다.
• 오른쪽/왼쪽/앞/뒤로는 인접한 경우에 해당되며, 대각선 방향은 해당되지 않는다.

해당 문제와 매우 유사한 문제에 대해 해설한 글을 아래에 첨부하니, 함께 참고하면 해결에 도움이 될 것이다. 

https://smary-it.tistory.com/412

[백준 BOJ] 7569번 토마토 (C++/cpp)

 

필자는 2차원 배열로 입력값을 받은 뒤, 큐를 통하여 너비 우선 탐색 연산을 진행하였다.

너비 우선 탐색(BFS)에 대한 개념이 생소하다면 해당 문제의 로직을 짜는 것이 어렵게 다가올 수도 있으니, 이 경우에는 우선 BFS와 큐에 대하여 먼저 파악한 뒤에 문제 해결을 시도해 볼 것을 권장한다.

입력값 범위 자체는 좁은 편으로, BFS 기본 원리만 잘 적용한다면 비교적 수월하게 해결할 수 있을 것이다.

보다 자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 상자의 크기(m, n)를 입력받는다.

 

2) BFS 연산을 위해, 아래처럼 큐와 배열을 미리 선언해 둔다.

- q1 :: 익은 토마토의 좌표 중 행 번호를 저장할 큐

- q2 :: 익은 토마토의 좌표 중 열 번호를 저장할 큐

- a :: 토마토의 배치에 대한 입력값을 저장할 배열

(실제 입력값들의 경계선까지 모두 배열에서 나타내기 위해, (n+2)*(m+2) 크기로 배열을 선언해 두었다.)

(차후에 배열 a는 각 위치의 토마토가 익는 데에 걸린 일수를 연산할 때에 활용될 예정이다.)

 

3) 토마토 정보를 입력받기 이전에, 배열 a에 할당된 배열값들을 우선 모두 -1로 초기화해 둔다.

(실제 입력값은 (1, 1) ~ (n, m) 내에 저장할 예정이며, 그 이외의 공간은 모두 입력의 경계로 간주할 예정이다.)

 

4) 2중 반복문을 활용하여, 입력을 하나씩 받아 이를 순차적으로 배열 a에 저장하도록 한다.

이때 a[i][j]의 값이 1인 경우를 찾았다면, q1과 q2에 각각 i, j 값을 삽입하도록 한다.

(차후에 그 인접한 값들에 대해 BFS 연산을 수행해야 하기 때문에, 익은 토마토의 위치는 모두 큐에 담아두어야 한다.)

 

5) q1과 q2가 빌 때까지, 반복문을 수행하여 아래의 연산을 취한다.

- 임의의 변수 i, j에 q1과 q2의 front값을 저장한 뒤, pop 연산을 통해 두 front 값을 각 큐에서 삭제한다.

- 현재 위치의 a 배열값을 받고, 그에 1을 더한 값을 임의의 변수 cnt에 저장하도록 한다.

- 현재 위치에 대해, 오른쪽/왼쪽/앞/뒤를 모두 탐색하도록 한다.

만약 4개 방향을 탐색해 보았을 때, 익지 않은 토마토를 발견하였다면 그 배열값을 현재의 cnt 값으로 설정한다.

그리고 이에 대한 차후의 BFS 연산을 이어가기 위해, 해당되는 좌표 정보를 각각 q1과 q2에 삽입하도록 한다.

 

6) 모든 토마토가 익은 일수를 저장할 변수 max를 0으로 초기화하여 선언해 둔다.

그리고 모든 토마토가 익었는지에 대한 여부를 저장할 변수 tf를 true 값으로 초기화하여 선언해 둔다.

 

7) 2중 반복문을 활용하여, a의 모든 배열값에 순차적으로 접근하여 값을 확인해 본다.

- 만약 현재 탐색하고 있는 배열값이 0의 값을 가진다면, 이는 모든 토마토가 익은 것이 아님을 의미한다. 따라서 이 경우에는, tf의 값을 false로 변경하도록 한다.

(코드에는 break문도 함께 있으나 없어도 실행 원리에는 차이가 없다.)

- 만약 현재 탐색하고 있는 배열값이 max보다 더 큰 값을 가진다면, max를 해당 값으로 갱신하도록 한다.

 

8) 위의 모든 연산이 완료되었다면, 아래와 같이 정답을 출력하고 실행을 종료한다.

tf의 값이 false라면 이는 모든 토마토가 익지 않았음을 의미하기 때문에 -1을 정답으로 출력하도록 한다.

다만 tf가 true값을 잘 유지하였다면, 최종적으로 저장된 max의 값에 1을 뺀 값을 정답으로 출력하도록 한다.

배열 a에는 모두 각 위치의 익은 토마토에 대해서 익은 일수에 1씩 더해진 값이 저장되어 있다고 볼 수 있다. 0일차부터 이미 익은 토마토의 입력값은 1이고, 그 1이라는 값에 점차 가산을 해나갔기 때문이다. 따라서 max 또한 정답에 1이 가산된 상태라 볼 수 있으므로, 여기에 1을 빼주어야 정답이라 할 수 있다.

반응형

 

성공한 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//백준 7576번 코드
public class Main {
    public static void main(String[] args) {
    	Scanner s=new Scanner(System.in);
		//입력부분
		int m=s.nextInt();//가로 크기
		int n=s.nextInt();//세로 크기
		int a[][]=new int [n+2][m+2];
		Queue<Integer> q1=new LinkedList<Integer>();
		Queue<Integer> q2=new LinkedList<Integer>();
		for(int i=0;i<n+2;i++) {
			for(int j=0;j<m+2;j++) {
				a[i][j]=-1;	
			}
		}
		
		for(int i=1;i<=n;i++) {//입력값 넣기
			for(int j=1;j<=m;j++) {
				a[i][j]=s.nextInt();
				if(a[i][j]==1) {q1.add(i);	q2.add(j);}
			}
		}
		
		//탐색부분
		while(!q1.isEmpty()&&!q2.isEmpty()) {
			int i=q1.peek();	int j=q2.peek();
			q1.poll();	q2.poll();
			int cnt=a[i][j]+1;
			if(a[i][j+1]==0) {
				a[i][j+1]=cnt;	q1.add(i);	q2.add(j+1);}
			if(a[i][j-1]==0) {
				a[i][j-1]=cnt;	q1.add(i);	q2.add(j-1);}
			if(a[i+1][j]==0) {
				a[i+1][j]=cnt;	q1.add(i+1);	q2.add(j);}
			if(a[i-1][j]==0) {
				a[i-1][j]=cnt;	q1.add(i-1);	q2.add(j);}
		}
		
		//출력부분
		int max=0;
		Boolean tf = true;
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				if(a[i][j]==0) { tf = false; break;}
				if(max<a[i][j]) {max=a[i][j];}
			}
		}
		
		if(tf == false) {System.out.println(-1);}
		else {
			System.out.println(max-1);
		}
    }
}

 

제출 결과

(2020.01.25 백준 7576번 문제 제출 결과)

너무 옛날 코드라 엄청 수정해서 업로드하였다