📘초기 풀이 (오답)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Crush_Wall_Move {
static int N,M;
static int[][] map;
static int[] dr = {1,0,0,-1};
static int[] dc = {0,1,-1,0};
static boolean flag = false;
static int answer = Integer.MAX_VALUE;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken())+1;
M = Integer.parseInt(st.nextToken())+1;
map = new int[N][M];
List<int[]> list = new ArrayList<>();
for (int i = 1; i < N; i++) {
String str = br.readLine();
for (int j = 1; j < M; j++) {
char c = str.charAt(j-1);
if(c=='0'){
map[i][j] = 0;
}
else {
map[i][j] = 1;
list.add(new int[]{i,j});
}
}
}
int len = list.size();
for (int i = 0; i < len; i++) {
int[] wall = list.get(i);
map[wall[0]][wall[1]] = 0;
bfs(1,1);
map[wall[0]][wall[1]] = 1;
min = Math.min(answer,min);
}
if(N==2&&M==2) {
System.out.println(1);
return;
}
if(!flag)
System.out.println(-1);
else
System.out.println(min);
}
public static void bfs(int row, int col){
Queue<int[]> que = new LinkedList<>();
int[][] copymap = map.clone();
copymap[1][1] = 1;
boolean[][] visited = new boolean[N][M];
que.add(new int[]{row,col});
while (!que.isEmpty()){
int[] current = que.poll();
int crow = current[0];
int ccol = current[1];
for (int i = 0; i < 4; i++) {
int nrow = crow+dr[i];
int ncol = ccol+dc[i];
if(ncol<1||nrow<1||nrow>=N||ncol>=M)
continue;
if(!visited[nrow][ncol]&&map[nrow][ncol]!=1){
visited[nrow][ncol] = true;
copymap[nrow][ncol] = copymap[crow][ccol]+1;
que.add(new int[]{nrow,ncol});
if(nrow==N-1&&ncol==M-1){
flag = true;
answer = copymap[nrow][ncol];
return;
}
}
}
}
}
}풀이방법
벽을 하나 부수고, bfs를 실행해서 최솟값을 출력하는 전형적인 bfs풀이였다.
주의할 점이 있다면, 그냥 count를 증가시키는게 아닌
copymap[nrow][ncol] = copymap[crow][ccol]+1;로 칸의 이동을 카운트 하는정도,
마지막에 도달하지 못한다면 -1를 출력한다.
하지만 이렇게 완전탐색으로 푼다면 시간초과에 걸려 문제를 통과하지 못한다.
📘정답 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Crush_Wall_Move {
static int N,M;
static int[][] map;
static int[] dr = {1,0,0,-1};
static int[] dc = {0,1,-1,0};
static boolean flag = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken())+1;
M = Integer.parseInt(st.nextToken())+1;
map = new int[N][M];
for (int i = 1; i < N; i++) {
String str = br.readLine();
for (int j = 1; j < M; j++) {
char c = str.charAt(j-1);
if(c=='0'){
map[i][j] = 0;
}
else {
map[i][j] = 1;
}
}
}
bfs(1,1);
if(!flag)
System.out.println(-1);
}
public static void bfs(int row, int col){
Queue<int[]> que = new LinkedList<>();
int crash = 0;
boolean[][][] visited = new boolean[N][M][2];
que.add(new int[]{row,col,1,crash});
while (!que.isEmpty()){
int[] current = que.poll();
int crow = current[0];
int ccol = current[1];
if(crow==N-1&&ccol==M-1){
System.out.println(current[2]);
flag = true;
return;
}
for (int i = 0; i < 4; i++) {
int nrow = crow+dr[i];
int ncol = ccol+dc[i];
if(ncol<1||nrow<1||nrow>=N||ncol>=M)
continue;
int next_cnt = current[2]+1;
if(map[nrow][ncol]==0){
if(current[3]==0 && !visited[nrow][ncol][0]){
que.add(new int[]{ nrow,ncol,next_cnt,current[3]});
visited[nrow][ncol][0] = true;
}
else if(current[3]==1 && !visited[nrow][ncol][1]){
que.add(new int[]{nrow,ncol,next_cnt,current[3]});
visited[nrow][ncol][1] =true;
}
}
else {
if(current[3]==0){
visited[nrow][ncol][1] = true;
que.add(new int[] { nrow,ncol,next_cnt,current[3]+1});
}
}
}
}
}
}
풀이방법
이 풀이의 핵심은
📢 큐에 1. 내가 벽을 부순적이 있는지 2. 다음카운트 3. 다음 행 4. 다음 열 이렇게 4가지를 넘기는것이 핵심이다.
마치 재귀호출에 인수로 넘기는 형태와 비슷한거 같다.
📢 크게 보면 다음 좌표가 1. 벽이 아닐때, 2. 벽일때로 나뉜다.
1. 벽이 아닐때는 이전에 1-1.벽을 부셨는지, 1-2.벽을 부신적이 없는지로 나뉜다.
2. 벽일때는 처음 벽을 부술때만 큐에 넣어준다. 이때 current[3]+1값으로 벽을 부셨음을 체크해준다.
📢최단거리는 다음 두 경우 중 하나에서 나온다.
1. 벽을 부수지 않고 목적지 까지 도달할 수 있을 때의 최단거리
2. 벽을 하나 부수고 목적지 까지 도달할 수 있을 때의 최단거리
하지만 방문체크시 벽을 부수고 먼저 탐색한 좌표가 부수지 않고 탐색한 좌표와 겹치게 되어 탐색이 제대로 안된다.
따라서 벽을 부순 방문map, 벽을 부수지 않은 방문map 두개를 사용하여 각각 체크해준다.
후기
이렇게 일정풀이를 막아논 문제 굉장히 싫다.. 진작에 알았다면 안풀었을듯
저 풀이를 생각하는것도 어려웠고, 보고 이해하는것도 어려웠다. 사실 지금도 100퍼센트 이해한거 같지는 않다.
그래도 큐에 다음 카운트를 담아서 넘기는 형태는 나중에도 많이 써먹을 것 같다.
그리고 풀이 코드에는 없지만 int c = str.charAt(j-1)-'0';
이렇게 하면 string '1'이 숫자 1로 들어가는데 이건 좀 유용한거 같다.
새로 알았다.
