4991번 (1) 썸네일형 리스트형 [백준] 4991번 : 로봇 청소기 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 해당문제는 다이나믹프로그래밍, 비트마스킹, 완전탐색, 깊이우선탐색, 너비우선탐색을 활용하여 문제를 해결 하였습니다. 너비우선탐색으로는 0과 *, *과* 사이의 거리를 구하였고, dp 테이블에 각각의 사이를 메모리제이션 하였습니다. 완전탐색과 깊이우선탐색, 비트마스킹으로 모든 경우의수를 방문 합니다. from sys import stdin from collections import deque input = .. 이전 1 다음