BOJ 7576 토마토

7576번: 토마토

이전에 포스팅했던 미로 탐색 문제와 거의 동일한 문제이다.

 

---

큐 자료구조를 이용한 BFS를 한번 더 포스팅하고자 한다. 이번에는 날짜를 다루는 변수를 큐에 넣지 않고 진행한다.

위와 같은 2x2 행렬을 이용하며, 문제의 입력 예제 중 3번을 이용하고자 한다.

 

 

입력을 받을 때, 0의 개수를 카운팅 하여 현재 익지 않은 토마토의 개수를 가지고 있어야 -1 (= 모두 익히는 방법이 없음)을 처리할 수 있다.

 

 

 

이전 포스팅과 동일하게 큐를 이용하며, 왼쪽의 흰 화살표 방향으로 데이터를 저장한다. (상단으로 입력, 하단으로 출력)

본 문제는 스택과 같은 다른 자료구조를 이용해도 문제없이 해결 가능하다.

---

문제를 풀기 위한 규칙은 간단하다.

 

• (규칙 A) 큐가 비지 않았다면, 큐에서 값을 하나 꺼내어 해당 값 근처의 익지 않은 토마토를 익힌다.
  • (규칙 A-1) 새로운 토마토를 익힐 때마다 익지 않은 토마토 변수의 값을 1씩 빼준다.
  • (규칙 A-2) 큐가 빌 때까지 규칙 A를 반복한다.
• (규칙 B) 큐가 모두 비었다면 이번 사이클 (=일차)에 새롭게 익은 토마토들을 큐에 넣어주고, 소요 날짜 변수를 하루 더해준다.
• (규칙 C) 큐가 모두 비었음에도, 새롭게 익은 토마토가 없다면 익지 않은 토마토의 개수를 확인한다.
  • (규칙 C-1) 익지 않은 토마토가 0개라면 그 순간의 소요 날짜를 답으로 출력한다.
  • (규칙 C-2) 익지 않은 토마토가 1개 이상이라면 토마토를 모두 익힐 수 없는 것이므로 -1을 답으로 출력한다.

 

규칙을 하나하나 따라가 보자.

 

0일 차, 즉 처음 시작한 순간의 행렬의 상태와 큐의 상태는 아래와 같다.

 

 

(규칙 A)에 의해 큐에서 값을 하나 꺼낸다.

 

 

 

1, A 근처의 안 익은 토마토들을 익게 만든다.

 

(규칙 A-2)에 의해 익지 않은 토마토 변수의 값이 1 빼 진다.

 

 

 

큐에 아직 값이 남아있기 때문에 (규칙 A-2)에 의해 다시 한번 (규칙 A)를 반복한다.

 

 

 

 

.

 

 

 

 

토마토를 한 개 더 익힌 뒤에는 (규칙 A-2)에 의해 다시 (규칙 A)로 가지 않는다.

 

 

 

대신 (규칙 B)에 의해 방금 익은 1, B 토마토와 방금 익은 6, D 토마토가 새롭게 큐로 들어간다.

 

 

 

이후 며칠이 지났는지를 나타내는 변수를 1 더해준다.

 

 

 (규칙 C)에 의해 종료될 때까지 위의 사이클을 반복하면 정답을 얻을 수 있다.

 

---

code

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지