티스토리 뷰
[JAVA] 백준 #7576 토마토🍅 | BFS 풀이 방법 | Deque와 Queue | 시간 초과 반례
YouJungJang 2024. 3. 21. 00:07
백준 #7576 토마토🍅
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
🔒 문제 설명
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
🔐 1차 시도: 시간 초과
우선 처음에 구성했던 로직은 다음과 같다.
[1] while문 한번 돌 때마다 days를 하나씩 늘려 누적해 나간다.
[2] while문 안의 첫 번째 for문은 box 배열을 탐색하면서 익은 토마토(1)를 찾는다.
익은 토마토를 찾으면 bfs 메서드를 호출해 사방탐색을 진행한다.
이때 중복 탐색을 제외하기 위해 visited [n][m] == 0 인 토마토에 대해서만 bfs를 호출한다.
[3] bfs 매서드에서는 사방탐색을 진행해 익은 토마토 근처에 안 익은 토마토(0)를 찾고, 그 값을 1로 바꿔준다.
[4] 이렇게 매일매일 값을 누적하며 진행하다가 하루 동안 아무 변화가 없을 경우,
- 만약, 배열에 0이 남아있다면 모든 토마토를 익게 할 수 없는 경우이므로 -1 출력
- 아니라면 누적한 days 출력
예를 들어, 아래와 같은 box [N][M]이 주어졌다고 하자.
box[N][M]
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1
그럼 while문을 통해 매일매일 익은 토마토를 탐색해 사방탐색을 통해 익은 토마토 주위의 안 익은 토마토를 0->1로 변경한다.
day 1
1 -1 0 0 0 0
1 -1 0 0 0 0
0 0 0 0 -1 1
0 0 0 0 -1 1
day 2
1 -1 0 0 0 0
1 -1 0 0 0 1
1 0 0 0 -1 1
0 0 0 0 -1 1
day 3
1 -1 0 0 0 1
1 -1 0 0 1 1
1 1 0 0 -1 1
1 0 0 0 -1 1
day 4
1 -1 0 0 1 1
1 -1 0 1 1 1
1 1 1 0 -1 1
1 1 0 0 -1 1
day 5
1 -1 0 1 1 1
1 -1 1 1 1 1
1 1 1 1 -1 1
1 1 1 0 -1 1
day 6
1 -1 1 1 1 1
1 -1 1 1 1 1
1 1 1 1 -1 1
1 1 1 1 -1 1
정답: 6그럼 맨 마지막 6일째에는 비어있는 부분을 제외한 모든 토마토가 1로 변경되므로 더 이상 변경할 수 있는 값이 없다.
그러므로 정답은 6
위 로직을 구현한 코드는 아래와 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] box;
static int[][] visited; // 중복 탐색 방지용
static int M, N;
static int[] X = { 0, 1, 0, -1 };
static int[] Y = { 1, 0, -1, 0 };
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer( bf.readLine(), " " );
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
box = new int[N][M];
visited = new int[N][M];
for( int n = 0; n < N; n++ ){ // 상자에 토마토 담기
st = new StringTokenizer( bf.readLine(), " ");
for( int m = 0; m < M; m++ ){
int tomato = Integer.parseInt(st.nextToken());
box[n][m] = tomato;
}
}
int days = 0;
while(true) {
boolean change = false; // 변화가 있었는지 확인
Deque<int[]> ripedTomato = new LinkedList<>();
for( int n = 0; n < N; n++ ){ // 현재 익은 토마토 위치 파악
for( int m = 0; m < M; m++ ){
if( box[n][m] == 1 && visited[n][m] == 0 ){
ripedTomato.offerFirst(new int[]{n,m});
visited[n][m] = 1;
}
}
}
while(!ripedTomato.isEmpty()){ // 현재 익은 토마토에 대해서만 사방탐색 진행
int[] location = ripedTomato.pollFirst();
if(bfs( location[0], location[1] )){
change = true;
}
}
if(!change){ // 하룻동안 변화가 없었는데 여전히 안익은 토마토가 있다면 -1 리턴
for( int n = 0; n < N; n++ ){ // 현재 익은 토마토 위치 파악
for( int m = 0; m < M; m++ ){
if( box[n][m] == 0 ){
System.out.println(-1);
System.exit(0);
}
}
}
break;
}
days ++;
}
System.out.println(days);
}
static boolean bfs( int n, int m ){
boolean change = false;
for( int i = 0; i < 4; i++ ){
int x = n + X[i];
int y = m + Y[i];
if( x < 0 || y < 0 || x > ( N - 1 ) || y > ( M - 1 ) ) continue;
else if( box[x][y] == 0 ) {
box[x][y] = 1;
change = true;
}
}
return change;
}
}
주어진 예제들에 대해 옳은 정답을 출력하지만, 틀린 풀이이다. 시간 초과가 되는 매우 비효율적인 코드이기 때문이다.
처음에는 시간 초과가 어디 부분에서 발생하는지 이해가 되지 않아서 어려웠다.
그런데 반례를 찾고 보니 원인은 간단했다.
⚠️ 시간 초과 반례:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
......
위와 같이 1이 하나만 있는 크기가 무수히 큰 배열이 있다고 해보자.
M, N의 크기가 최대 1000 이하라고 했으니 1000 X 1000 크기의 배열에서 익은 토마토는 하나만 있다고 해보자.
그럼 내가 1차 시도에서 구현한 코드는 while문에서 1 하나를 찾으려고 매일 배열을 1000번씩 돌아야 한다.
이런 식으로 생각해 보니 내 코드의 시간 복잡도는 무려 O(N^2M^2)이다.
그러므로 새로운 풀이에는 과감히 while문은 빼고 큐를 사용해서 토마토 박스 값을 누적해 가는 방법을 사용했다.
로직은 다음과 같다.
[1] 입력을 받을 때, 익은 토마토를 덱에 삽입한다( offerFirst )
[2] 덱에서 하나씩 꺼내와서 사방탐색을 진행한다. -> bfs
[3] bfs에선 좌표와 day를 매개변수로 받는데, 자신이 영향을 받은 익은 토마토의 box [n][m] 값을 가져와서 내 박스 값을 누적한다.
[4] 덱이 빌 때까지 사방탐색을 진행한다. -> 덱이 비었다면 더 이상 사방탐색할 토마토가 없다는 뜻
[5] 그럼 이제 box배열을 돌면서 최댓값을 찾고, 0이 나오면 -1을 출력, 아니라면 최댓값-1을 출력한다.
실제로 구현한다면, 아래와 같은 토마토 박스가 주어졌을 때
box[N][M]
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1
큐를 돌리면서 사방탐색이 진행되어 값이 누적되어 마지막엔 box 배열이 다음과 같이 변화한다.
1 -1 7 6 5 4
2 -1 6 5 4 3
3 4 5 6 -1 2
4 5 6 7 -1 1
정답: 6
코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] box;
static int[][] visited; // 중복 탐색 방지용
static int M, N;
static int[] X = { 0, 1, 0, -1 };
static int[] Y = { 1, 0, -1, 0 };
static Deque<int[]> tomatoes;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer( bf.readLine(), " " );
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
box = new int[N][M];
visited = new int[N][M];
tomatoes = new LinkedList<>();
for( int n = 0; n < N; n++ ){ // 상자에 토마토 담기
st = new StringTokenizer( bf.readLine(), " ");
for( int m = 0; m < M; m++ ){
int tomato = Integer.parseInt(st.nextToken());
box[n][m] = tomato;
if(tomato==1) tomatoes.offerFirst(new int[]{n,m,1});
}
}
while(!tomatoes.isEmpty()){ // 익은 토마토 사방 탐색 진행
int[] index = tomatoes.pollLast();
bfs(index[0],index[1],index[2]);
}
int max = 0;
for( int n = 0; n < N; n++ ){
for( int m = 0; m < M; m++ ){
if( box[n][m] == 0 ){ // 안익은 토마토 있으면 -1
System.out.println(-1);
System.exit(0);
}
else if( max < box[n][m] ){ // 최소 소요일은 max - 1
max = box[n][m];
}
}
}
System.out.println( max - 1 );
}
static void bfs( int n, int m, int day ){ // 사방탐색
for( int i = 0; i < 4; i++ ){
int x = n + X[i];
int y = m + Y[i];
if( x < 0 || y < 0 || x > ( N - 1 ) || y > ( M - 1 ) ) continue;
else if( box[x][y] == 0 ) {
box[x][y] += ( day + 1 );
tomatoes.offerFirst(new int[]{x,y, box[x][y]});
}
}
}
}
비슷한 문제 추천:
2021 카카오 채용연계형 인턴십 기출문제: 거리두기 확인하기
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
'Study > JAVA' 카테고리의 다른 글
| [JAVA] 프로그래머스 : 기사단원의 무기 | 시간 초과 원인과 해결 방법 | 약수를 효율적으로 구하는 방법 (2) | 2024.04.04 |
|---|---|
| [JAVA] 프로그래머스: 주차요금 계산 | ArrayList to Array | 2차원 배열 정렬하기 | Comparator (0) | 2024.03.28 |
| [JAVA] 프로그래머스: 거리두기 확인하기 | Queue와 LinkedList | BFS 풀이 방법 (0) | 2024.03.19 |
| [JAVA] 백준 #1389 케빈 베이컨의 6단계 법칙 문제 풀이 | Floyd Warshall 알고리즘 (0) | 2024.03.13 |
| [JAVA] 프로그래머스 : 가장 많이 받은 선물 문제 풀이 | Map과 ArrayList (0) | 2024.03.05 |