2665 미로만들기

1,1 부터 n,n으로 가는데 사이사이가 끊켜져있어서 갈수가 없다. 이 때 칸을 매꿔서 통로를 만들려고 할 때, 매꿔야하는 칸의 최소값을 구하는 문제이다.

매우 난해한 문제였는데, 여러 수행착오 끝에 정답을 맞은 방법은 다음과 같다.
각 칸에 대응하는 매꿔야 하는 숫자 배열 point[n][n]을 선언하고, 최대값으로 초기화한다. 1,1부터 n,n까지 반복하면서 자신의 위치의 point 값과 자신의 왼쪽, 자신의 위 point 값의 최소값을 고른다. 그 다음 현재 위치가 끊켜져 있다면 1을 더해준다.

그렇게해서 n,n까지 반복했다면 point[n][n]의 값이 정답이 된다.
단, 이 때 point 배열의 초기 설정이 또 필요한데, 이것은 재귀를 이용해서 처음위치부터 밟을수 있는 모든 칸의 point 값을 0으로 주었다. 그런데 이것이 왜 제대로 동작하는지 나도 잘 모른다. 다른사람들에게 질문해봐야 겠다.

현재 이것은 잘못된 풀이로, 나중에 제대로된 정답을 맞으면 수정할 예정이다.

소스