섹션 8. DFS, BFS 활용 12. 토마토(BFS)

문제

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

• 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면,
• 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
• 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며,
• 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
• 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때,
• 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라.

입력

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

출력

• 첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 
• 도착할 수 없으면 -1을 출력한다.

입출력 예제

---

풀이방식

이번 문제는 BFS에 대한 문제이다.

 

---

설계과정

1. 이동 방향을 담은 배열 dy, dx에 값을 넣어서 저장한다.

2. 큐를 선언하고, 큐에 미리 선언한 Point 객체 값을 넣는다.

3. 출발점은 무조건 방문하므로 1을 넣는다.

4. 경계선 안쪽이고 통로라면 지나갈 수 있는 곳이므로 board 배열에 1을 넣어서 방문기록을 남긴다.

5. 큐에 현재 좌표 값을 넣고 dis 배열에 좌표값에 1을 더한 값을 넣는다.

6. 통로 끝까지 왔을 때에 값이 0이라면 -1을 출력하고, 아니라면 해당 값을 출력한다.

---

풀이과정

1. 각 변수들을 선언한다.

• 행의 이동 좌표를 위한 배열 dx[ ] 을 선언한다.
• 열의 이동 좌표를 위한 배열 dy[ ] 을 선언한다.
• 방문 기록을 저장할 배열 board[ ] 을 선언한다.
• 현재 좌표에서 이동할 수 있는 방향을 알기 위해 nx, ny를 선언해서 dx[ ], dy[ ] 배열의 값을 각각 더해준다.
• 걸리는 일자를 저장할 2차원 배열 dis[ ] 을 선언한다.

2. 큐를 생성하고 큐에 포인트 객체 값을 넣어준다.

• 미리 생성한 PointTwo 객체를 말하며, 이는 현재의 x, y 좌표값을 의미한다.

3. board 배열에서 좌표 값이 1이라면 익은 토마토이므로 큐에 좌표값을 넣는다.

• 익은 토마토들이 0레벨, 시작점이므로 큐에 미리 다 넣어놓는다.

4. Q.poll() 을 통해 큐에서 좌표값을 빼서 nx와 ny에 각각 dx[ ], dy[ ] 배열 값들을 더하는 for문을 돌린다

• tmp에 큐에서 꺼낸 현재 x,y 좌표값을 넣고 그 값에 각각 dx[ ], dy[ ] 값을 더해서 상하좌우 이동 좌표 값을 구한다.

5. 익지 않은 토마토라면 board[nx][ny]에 1을 넣어준 후 재귀함수를 호출한다.

• 1을 넣어주면 익은 토마토가 된다는 것을 의미한다.

6. 큐에 현재의 좌표 값을 넣어서 새 객체 값을 넣어준다.

 

7. dis[nx][ny] 에 현재의 x,y 좌표값을 넣은 후 1을 더해서 저장한다.

• dx[ ], dy[ ] 배열을 통해 상하좌우로 이동한 좌표에 방문한다는 의미이기에 1을 더해준다.

8. board[ ][ ] 배열 값이 0이라면 flag에 false를 넣고 -1을 출력한다.

• board 배열에 0이 있다는 것은 익지 않은 토마토가 존재한다는 의미이기에 -1을 출력한다.

9. 0이 아니라면 최대값을 리턴한다.

• 가장 오래 걸리는 일자를 출력한다.

---

더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.