[파이썬] 백준 2665번: 미로만들기

백준 2665번: 미로만들기 2665번: 미로만들기 문제 n×n 바둑판 모양으로 총 n 2 개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다. 시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 ... www.acmicpc.net 접근 방법 (핵심 아이디어) visited[y][x]를 (y,x) 칸까지 가기 위해 바꿔야 하는 방의 최솟값으로 정의하면 된다. 어려운 문제는 아님. 방문체크 대신에 바꿔야 하는 방의 최솟값으로 채워나가면 항상 최솟값이 들어있다. 일반적인 bfs로도 가능하지만, 우선순위...

원문링크 : [파이썬] 백준 2665번: 미로만들기