16946

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 1. Logic 여러가지 방법으로 시도해봤다. 시도한 방법은 1. DFS : DFS로 벽인 부분에서 이동할 수 있는 공간의 크기를 세서 저장했다. 100만개 탐색을 100만번 하니 당연히 터질 수 밖에. 그래서 DP로 접근했다. 2. DP : 한 정점에서 다른 정점으로 가는 방법을 DP로 하면 방향이 일정하기 때문에 값이 구해지지만 이번 문제는 상하좌우를 판단해야 하기 때문에..