[JAVA / 자바] 백준 7576번 - 토마토

 문제 

 

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

---

 입력 

첫 줄에는 상자의 크기를 나타내는 두 정수 M, N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M, N ≤ 1,000이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

---

 출력 

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

---

---

 문제 접근 방법 

익은 토마토 주변 상하좌우에 있는 토마토는 다음 날 익는다고 한다. 따라서 익은 토마토 주위의 토마토들을 구해 상하좌우에 인접해있는 토마토들이 익는 마지막 날까지 진행시켜 최대한으로 토마토를 익혔을 때 총며칠이 걸리는지와 안 익는 토마토가 있는지를 판단해주면 되는 문제이다.

따라서 이번 문제에서 쓰일 알고리즘은 너비 우선 탐색(BFS, Breath First Search) 알고리즘이다.

 

BFS알고리즘에서 필요로 하는 정보는

 

1. 다음 이동할 위치는 어디인가? - queue <>()

    ㄴ 익은 토마토의 주변 상하좌우에 있는 토마토가 익는 것이므로 익은 토마토의 위치를 큐에 저장해야 하는데, 첫날 익은 토마토는 한 개로 정해주지 않았기 때문에 여러 개 일 수도 있다. 따라서 그렇다면 토마토의 정보가 입력될 때, 익은 토마토는 모두 queue에 넣어두고 시작한다. (bfs함수에서 넣어도 되지만 최대한 반복문을 줄이기 위해 나는 토마토 정보가 입력될 때 같이 처리했다.)

 

2. 해당 위치를 방문했는가? - visited []

    ㄴ 나는 visited배열을 새로 선언해 주지 않고 방문 여부를 판단할 수 있는 방법을 생각해 보았을 때, 초기 토마토 배열이 0, 1, -1로 저장이 될 것이다. 그렇다면 어차피 dfs를 하면서 해당 위치에 있는 토마토가 며칠째에 익었는지 저장해 둘 배열이 또 필요했을 텐데(물론 새로운 클래스를 정의하여 변수로 저장할 수 있음) 그렇게 메모리를 또 차지하는 것보다 토마토 배열을 수정해서 해당 위치 방문 여부를 체크할 수 있다고 판단했다.

     ㄴ 토마토 배열을 수정하는 방법은 해당 위치에 토마토가 며칠째에 익었는지를 해당 위치에 저장하는 것이다. 그렇게 된다면 해당 위치에 저장된 숫자가 0이 아니면 해당 위치는 이미 방문한 것이 되기 때문에 굳이 visited배열을 정의해주지 않아도 방문 여부를 판단할 수 있게 된다.

 

두 가지가 있을 것이다.

 

위 방법을 토대로 bfs함수가 연산을 끝내면 이제 안 익은 토마토가 있는지 판단해서

안 익은 토마토가 남아있으면 -1을 출력하고 

모든 토마토가 익었으면 마지막 토마토가 익은 날짜를 출력해주면 된다.

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

이번 문제는 최단 경로를 찾는 문제와 비슷하다고 생각이 들었다.두 문제의 공통점은 출발 위치에서 도착 위치까지 걸리는 최단 거리(시간)를 찾는다는 점이고,두 문제의 차이점은최단 경로 문제는 도착지점이 정해져 있어 해당 위치에 저장된 값을 출력하면 되지만,토마토 문제는 도착지점이 정해져 있는 것이 아니라 마지막에 전체를 다시 탐색하면서 안 익은 토마토는 없는지 만약 안 익은 토마토가 없다면 제일 늦게 익은 토마토는 며칠이나 걸려서 익었는지를 출력한다는 점이다.문제를 푸는 논리는 두 문제가 비슷하기 때문에 해당 문제를 어떻게 풀 지 고민하는데 큰 어려움은 없었다는 생각이 든다.

---

 문제 원본 

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

 알고리즘 분류 

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색