백준 B4991-로봇 청소기 with 파이썬

문제 4991번: 로봇 청소기 문제 오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다. 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다. 일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러... www.acmicpc.net 풀이 이 문제는 2번의 시간초과와 한번의 틀렸습니다로 해결한 문제다. 틀렸습니다는 코드 실수로 발생했고 시간초과는 풀고 나니 이해가 되는 부분이다. 어차피 모든 좌표 별로 거리는 변하지 않으니깐 미리 좌표끼리의 최단 거리를 구하고 백트래킹을 진행하는게 좋은 방식인 것 같다. 코드 import ...

원문링크 : 백준 B4991-로봇 청소기 with 파이썬