11주차 과제: (2) 백준 2638 치즈

[jungyoonoh]

치즈 문제를 풀어주세요
https://www.acmicpc.net/problem/2638

[Seon-Ju]

https://github.com/Seon-Ju/unit-study/blob/main/Seonju/Baekjoon/Graph%20Traversal/2638_%EC%B9%98%EC%A6%88.py

1. 좌표값이 공기인 곳을 따라 BFS 진행
2. 모서리에는 치즈가 놓여있지 않다고 했으니 모서리는 모두 공기이므로 BFS 시작지점을 모서리 중 아무 곳이나 잡아도 됨 (저는 (0, 0)으로 잡았어요)
3. 공기의 상하좌우를 살피는데
   • 치즈가 놓여있다면 나중에 한번에 녹여주기 위해 melt에 저장하고, 공기와 한 면 접했다는 의미로 좌표값을 1 늘려줌
     공기와 여러 면 접한 치즈의 경우 melt에 중복저장되기 때문에 중복처리를 위해 melt를 set으로 선언했음
   • 공기가 놓여있다면 이 공기를 따라 BFS를 계속 진행해야 하므로 큐에 저장하고 방문처리
4. 공기 큐가 비게 되면 그 때 치즈를 한꺼번에 녹여주고 녹인 치즈 개수 리턴
5. 초기상태의 치즈 개수에서 녹인 치즈 개수를 빼서 치즈가 다 녹았다면 시간 출력하고 종료

✅ 완료

[jungyoonoh]

https://github.com/jungyoonoh/unit-study/blob/main/Yoonoh/Baekjoon/GraphTraversal/2638_%EC%B9%98%EC%A6%88.py

1. 치즈의 영역 탐색 -> 처음에 여기서 헤맸는데 문제에 있는 저게 힌트였다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.

전체가 1인 치즈 보드를 먼저 만들고 공기의 영역을 기준으로 BFS 돌아서 전부 0으로 변환해주면 치즈 덩어리 획득

2. 치즈 덩어리 정보를 먼저 확보하고, 치즈 위치 정보를 리스트에 담아둔다.
3. 각 치즈가 공기로부터 2면이상 닿아있는지 확인 후, 녹인 정보는 기존 board에 반영시킨다.
4. 판 찾고 녹이는 한 사이클을 1시간으로 가정, 치즈 영역 탐색 카운트 == 보드 사이즈일 경우 종료

✅ 완료