네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 2. 풀이과정 1. 0이 모여있는 구간마다 0의 개수를 센다. 2. 벽에서 4방향을 보면서 인접한 0의 구역에 있는 0의 개수를 더해준다. import java.io.*; import java.util.*; public class Boj16946 { static int N, M, map[][], no; static int dx[] = {-1, 0, 1, 0}, dy..

1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 풀이과정 최단거리 구하기는 보통 bfs, 도착지점까지 경로를 구한다면 dfs를 주로 사용하는 것 같다. 이 문제는 최단거리를 구하는 문제로 bfs를 사용하여 풀었다. 최단거리만큼만 모든 경로를 탐색하기 때문에 최악의 경우(모든 경로 끝까지 전체탐색)을 막을 수 있다. 처음에는 boolean visited[N][M][2]로 3차원배열을 사용해서 visited..

1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 풀이 과정 일반 DFS 문제와 다른점은 벽을 부수고 이미 지나간 경우보다 벽을 안 부수고 돌아서 다시 지나갈 때가 더 길지만 이 값도 저장해두어야 한다. 나중에 나온 벽을 부수고 갔을 때가 최단 경로가 될 수 있기 때문이다. 아래는 추가적으로 테스트 케이스를 만든 것이다. 입력 : 6 5 00000 11110 00000 01111 01011 00000 출력..