1944
-
[백준]1944: 복제 로봇 - JAVA문제풀이/백준 2021. 8. 14. 19:26
[백준]1944: 복제 로봇 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 풀이 🪑 이 문제는 어떻게 풀어야 하는지 도저히 모르겠었던 문제였다! 로봇이 움직이는 횟수의 합을 최소로 하기 위해서 BFS를 떠올렸지만, K를 만날 때마다 복제가 된다는 조건 때문에 방문 체크를 어떻게 처리해야 할지 걱정되었던 문제였다. 그래서 문제의 '알고리즘 분류'에서 MST라는 힌트를 얻었다. 막상 MST라는걸 알고 나니 되게 쉽게 느껴졌던 문제였다. 📝 문제를 정리해 보자! 모든 열쇠를 찾으면서..