백준 4991번 - 로봇 청소기
https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 필요한 배경지식 1번 풀이 : DFS, BFS 2번 풀이 : BFS, 외판원 문제(TSP) 3번 풀이 : BFS, DP, 비트마스킹 문제 해결 방법 방의 크기가 최대 20*20이므로 최단경로를 구하기 위해 BFS를 한번 수행하는 시간은 크게 문제가 되지 않습니다. 더러운 칸의 개수가 10개이므로 BFS를 최대 11번 수행하여 모든 더러운 칸과 로봇청소기 사이의 거리를 어렵지 않게 구할 수 있습니다. (di..
알고리즘 공부/문제풀이
2021. 6. 1. 00:26
반응형