미로 만들기
면접 대비시간 제한1초메모리 제한128 MB
n x n 격자에서 왼쪽 위부터 오른쪽 아래까지 이동 가능하도록 만들려면 최소 몇 개의 검은 방을 흰 방으로 바꿔야 하는지 0-1 BFS로 구하는 문제입니다.
문제
n × n 격자에는 총 n^2개의 방이 있다. 각 방은 흰 방 또는 검은 방이다. 흰 방에는 들어갈 수 있고, 서로 한 변을 맞댄 두 흰 방 사이에는 지나갈 수 있는 문이 있다. 검은 방은 벽으로 막혀 있어 그대로는 들어갈 수 없다.
시작 방은 왼쪽 위 칸이고, 끝 방은 오른쪽 아래 칸이다. 두 방은 항상 흰 방이다. 시작 방에서 끝 방까지 이동할 수 있도록 필요한 경우 검은 방을 흰 방으로 바꿀 수 있다.
검은 방을 흰 방으로 바꾸는 횟수를 최소화하려고 한다. 시작 방에서 끝 방까지 갈 수 있게 만들기 위해 바꾸어야 하는 검은 방의 최소 개수를 구하라. 처음부터 이동할 수 있다면 답은 0이다.
입력
첫 줄에 한 줄에 있는 방의 수 n이 주어진다. (1 ≤ n ≤ 50)
다음 n개 줄에는 길이가 n인 문자열이 하나씩 주어진다. 각 문자는 0 또는 1이며, 0은 검은 방, 1은 흰 방을 뜻한다.
출력
시작 방에서 끝 방까지 갈 수 있도록 흰 방으로 바꾸어야 하는 검은 방의 최소 개수를 출력한다.