연습 - [BOJ] 7576. 토마토 (Java)

문제 링크 / level: Silver I

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

7576번: 토마토

 

 

내가 생각한 풀이

요 며칠 BFS를 공부하면서 관련 문제를 풀고 있어서 도전하게 된 토마토 문제. BFS의 바이블 같은 문제라고 한다.

하지만 그동안 풀었던 단지번호붙이기, 그림, 미로 탐색과 같은 BFS 문제들보다는 더 어려운 느낌이 들었다.

 

왜냐하면 토마토가 점점 퍼져나가는데 이를 어떻게 제대로 처리할 것인가?에 대한 아이디어를 떠올리는 것이 관건이었기 때문이고, 도저히 생각이 나질 않아서 힌트를 봤더니 '큐'를 사용하라는데 그래도 잘 모르겠더라.😭 (흙흙,,)

우선은 어떤 것의 최소를 구하라고 하니 이건 BFS 문제구나-하는 감이 와야할 것이다. 내가 만약 이게 BFS 문제라는 것을 모르고 풀었다면...?

 

 

#1.

일단 내가 할 수 있는 것은 저장될 때부터 모든 토마토가 익어있는 상태라면 0을 출력하고 종료하는것 뿐이니 이것부터 처리하기로 했다. (1: 익은 토마토, 0: 익지 않은 토마토, -1: 그 자리에 토마토가 없는 경우)

'모든 토마토가 익어있는 상태'라는 말의 의미는 결국 토마토 배열의 원소 중 0이 하나도 없다는 뜻과 같다.

1과 -1는 얼마가 있든 '익지 않은 토마토의 개수'와는 전혀 상관 없으니까.

 

그래서 내가 생각한 방법은 처음 배열의 원소값들을 입력받을 때 firstCheck라는 변수를 두고 초기값을 0으로 설정한 뒤에 원소가 하나 입력될 때마다 얘가 0인지 아닌지를 체크하는 것이다. 그리고 값이 0인 원소가 하나도 없다면, 즉, 배열의 모든 원소값을 입력받고 for문을 벗어났을 때 firstCheck의 값이 그대로 0이라면 익지 않은 토마토가 하나도 없다는 뜻이겠다.🤗👍

 

for (int i = 0; i < N; i++) {
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		for (int j = 0; j < M; j++) {
			tomato[i][j] = Integer.parseInt(st2.nextToken());
			if(tomato[i][j]==0) {firstCheck++;}
		}
	}
	// 저장될 때부터 모든 토마토가 익어있는 상태라면 종료
	if(firstCheck==0) {
		System.out.println("0");
		return;
	}

 

이런 식으로 말이다. 여기까지는 잘 돌아가는 것 같다.

 

흐음,,,,

 

#2.

이제부터가 문제인데, 내가 풀었던 BFS 문제들처럼 그냥 배열의 원소들을 하나씩 검사하면 끝나는 문제가 아닌 것 같다.

왜냐하면 하루가 지나면 창고에 있는 토마토 중 모든 익은 토마토의 상하좌우에 있는 토마토가 한꺼번에 익어야하기 때문이다. 쉽게 말해서 배열 내의 원소들을 하나씩 돌면서 bfs 처리를 해주는 것이 아니라 익은 상태인 모든 토마토에 대하여 동시에 bfs를 진행해주어야 한다는 뜻이다.

 

그걸 도대체 어떻게 처리해주지?라는 생각이 머리를 스치고...

힌트는 '큐'라는데.. 혼자 고민해서는 도저히 답이 나오지 않을 것 같아 도움이 될만한 글들을 찾아보았다.

여러 사람들의 코드를 살펴보고 이렇게 저렇게 쿵짝쿵짝 이해를 해본 결과는 이랬다.🤔

 

*중요: 하루에(동시에) 여러 개의 토마토에 대해 bfs를 진행해야하므로 시작점이 정해져있지 않고, 따라서 bfs의 인자는 없다.

1. 기존의 BFS 문제들과는 달리 큐를 2개 만든다. (1개는 오늘 새롭게 익은 토마토들 저장용: tq, 다른 1개는 bfs 처리용: que)

2. tq의 모든 원소들을 que에 넣어준다. 얘네를 가지고 bfs를 돌려줄거다.

3. que에 들어있는 원소들을 가지고 내가 알고 네가 아는 그 bfs 로직을 만들어준다. 이때 새로운 익은 토마토가 생성될 때마다 그 좌표를 tq에 추가해준다. 다음날이 되면 처리해줄 녀석들이다. 또한, 하루에 여러 개의 토마토가 익을테니 visited 배열의 값을 업데이트할 때도 주의해야한다.

4. 3번 로직은 que가 비어있지 않는 동안 반복되는데, 그 반복이 끝나면 n일차 토마토 익기 대회가 끝난 것이다.

5. que가 텅 비어있다면 다시 tq를 살펴보고 tq까지 비어있으면 bfs는 그대로 끝. 비어있지 않다면 2~4번의 로직을 반복해준다.

 

참 쉽죠잉?😂 

나는 이 로직을 수행할 때 동시에 dayCnt라는 변수에 1씩 추가해서 날짜도 같이 카운팅해줬다. (n일차 토마토 bfs가 끝날 때마다) 단, 마지막에 tq가 비어있는 것을 확인하고 while문을 빠져나올 때 dayCnt가 추가로 한 번 더 카운팅되므로 최종결과를 출력할 때는  dayCnt 값에서 -1 해주는 요령이 필요하다.

 

 

#3.

가장 마지막에 처리해줄 것은 '만약 토마토가 다 익지 못하는 상황이라면?'에 관한 것이다.

예를 들어, 사방에 토마토가 없다면 그런 상황이 발생할 수가 있겠다.

만약 모든 bfs를 처리한 후의 토마토 배열에 아직 익지 않은 토마토가 남아있다면 그때가 바로 토마토가 다 익지 못하는 상황일 것이다.

 

<토마토 배열>

위: 처음 상태 / 아래: bfs 후

위: 처음 상태 / 아래: bfs 후

따라서 이를 코드로 구현하려면 bfs를 처리해준 뒤에 토마토 배열을 순회하면서 배열 원소 중에 0이 있는지를 체크하면 된다.

그리고 만약 0이 있다면 최종 출력값을 -1로 업데이트 해주고 프로그램을 종료시킨다.

이 부분은 따로 메소드를 만들어서 빼줄 수도 있고, 메인함수에서 바로 처리해줄 수도 있을텐데 나는 메인함수에서 처리해줬다.

 

그리고 정말 진짜 마지막으로 토마토가 다 익는데 걸린 날짜를 출력해야하는데, 나는 dayCnt 변수를 이용해서 처리해줬다.

 

// 핵심 코드
private static void bfs() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if(tomato[i][j]==1) { // 익은 토마토가 있다면
				visited[i][j] = 1; // 방문표시 하고
				tq.offer(new int[] {i,j}); // tomato que에 넣어준다.
			}
		}
	}
	while(!tq.isEmpty()) {
		int size = tq.size();
		// tomato que에 있는 좌표들을 꺼내서 bfs que에 넣어준다.
		for (int i = 0; i < size; i++) {
			que.offer(tq.poll());
		}
		while(!que.isEmpty()) {
			int[] curr = que.poll();
			int cy = curr[0];
			int cx = curr[1];
			for (int d = 0; d < 4; d++) {
				int ny = cy + dy[d];
				int nx = cx + dx[d];
				if(!check(ny,nx)) {continue;}
				if(tomato[ny][nx]==0 && visited[ny][nx]==0) {
					visited[ny][nx] = visited[cy][cx]+1;
					tq.offer(new int[] {ny,nx});
					tomato[ny][nx] = 1;
				}
			}
		}
		dayCnt++;
		// 마지막에 tq에 원소가 하나도 없어서 빠져나올 때도 1이 더해짐.
	}
}

 

BFS 알고리즘 계의 교과서와도 같다는 백준의 토마토 문제를 드디어 풀어보았다.🍅 (왕뿌듯)

정확히 이해를 해서 내 입맛에 맞게 코드를 작성하기는 했지만 다른 사람들의 도움을 받아서 푼 것이나 마찬가지니까 시간차를 두고 다시 풀어볼 생각이다. 그때 코드 전문을 같이 올리도록 하겠다. 그럼 20000~🙋‍♀️👋