b2206_벽부수고이동하기;

b2206_벽부수고이동하기;

https://www.acmicpc.net/problem/2206

package com.BFS.b2206_벽부수고이동하기; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; // 1,1 ~ N,M 까지 가는길의 총합이 1이거나 0일때 "최단거리" public class Main { static int N; static int M; // 우 하 좌 상 static int [] dr = {0,1,0,-1}; static int [] dc = {1,0,-1,0}; static int [][] map; static int [][] min; static boolean [][][] visited; 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()); // 행 M = Integer.parseInt(st.nextToken()); // 열 map = new int[N+1][M+1]; min = new int[N+1][M+1]; // 해당 좌표까지 가기 위해 이동한 거리를 저장 visited = new boolean[N+1][M+1][2]; // r,c,0 : 벽없을때 / r,c,1 : 벽있을때 // 입력 String str; for (int r = 1; r <= N; r++) { str = br.readLine(); for (int c = 1; c <= M; c++) { map[r][c] = str.charAt(c-1)-'0'; // 0 빈방, 1 벽 } } System.out.println(bfs(new int[]{1,1})); //print(); br.close(); } private static int bfs(int [] v) { Queue queue = new LinkedList<>(); queue.add(new int[]{v[0],v[1],0,1}); // {r,c,지금까지 벽을 부셨던적이 있는지 없는지 정보를 담기 위함(부셨으면 1 안부셨으면 0)} // 벽부신적있는지의유무를 매번 갖고 다녀야함!!! 그래야 다음 경로를 갈수있는지 없는지 판단할수있기때문 min[v[0]][v[1]]=1; visited[v[0]][v[1]][0] = true; int nr; int nc; while (!queue.isEmpty()){ v = queue.poll(); int crash = v[2]; // 제일 처음에 N,M에 도착한경우가 최단거리이므로 N,M에 도착했을때 리턴해주기 if(v[0]==N && v[1]==M) return min[N][M]; for (int d = 0; d < 4; d++) { nr = v[0] + dr[d]; nc = v[1] + dc[d]; if(nr<1||nc<1||nr>N||nc>M) continue; // 벽인데 방문안한곳 (부신적 없는 벽)...... 을 방문하기 위해서는 이전에 벽을 부신적 있으면 안됨 // visited -> r,c,0 : 벽없을때 방문 확인 / r,c,1 : 벽있을때 방문 확인 // crash : 벽을 부신 전적유무(이전에 벽을 부신적이 있다면 실행 x) if(map[nr][nc]==1 && !visited[nr][nc][1] && crash==0) { visited[nr][nc][1] = true; // 무조건 벽을 부신경우의 방문이니까 1 min[nr][nc] = min[v[0]][v[1]] + 1; // 이동수 증가 queue.add(new int[]{nr, nc, 1}); // 부신걸 체크(1표시)하고 다음 경로 탐색하기위해 큐에 넣어줌. 이때 crash 자체를 1로바꾸면 안된다. // 왜냐면 추후에 여기서 넣은 큐의 탐색이 종료되고 다음 큐를 탐색할때!! 부신걸 다시원래대로(안부셨다고)해야하기 때문에 crash를 1로 바꾸지 않는다 } // 벽을 부셨는지 안부셨는지 상관없이 방문여부만 확인하고 실행 if(map[nr][nc]==0 && !visited[nr][nc][crash] ){ visited[nr][nc][crash]= true; // crash : 벽을 부셨는지 안부셨는지 상관없이 실행되기때문에, 이전에 부셨는지 안부셨는지에 따라 방문표시 min[nr][nc] = min[v[0]][v[1]] + 1; queue.add(new int[]{nr,nc,crash}); // 큐에 넣는것도 방문표시와 마찬가지로, 부숨유무를 넣어준다 } //print(); } } return -1; // 위에서 리턴하지 못하는 경우는 N,M에 도착하지 못하는 경우 } private static void print() { for (int r = 1; r <= N; r++) { for (int c = 1; c <= M; c++) { System.out.print(min[r][c]+" "); } System.out.println(); } System.out.println("----------"); } } /* 5 5 00000 11101 00001 01111 00010 */

package com.BFS.b2206_벽부수고이동하기; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; // min 배열을 만들지 않고 큐에 같이 담아서 증가시키는 코드 public class Main2 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); int [][]map = new int[N][M]; String str; for (int r = 0; r < N; r++) { str = br.readLine(); for (int c = 0; c < M; c++) { map[r][c] = str.charAt(c)-'0'; } } System.out.println(bfs(map,N,M)); br.close(); } private static int bfs(int [][] map,int N, int M) { int [] dr = {0,1,0,-1}; int [] dc = {1,0,-1,0}; Queue queue = new LinkedList<>(); boolean [][][] visited = new boolean[N][M][2]; queue.add(new int[]{0,0,0,1}); visited[0][0][0] = true; int [] v; int nr; int nc; int crash; int min; while (!queue.isEmpty()){ v = queue.poll(); crash = v[2]; min = v[3]; if(v[0]==N-1 && v[1]==M-1) return min; for (int d = 0; d < 4; d++) { nr = v[0] + dr[d]; nc = v[1] + dc[d]; if(nr<0||nc<0||nr>=N||nc>=M) continue; if(map[nr][nc]==1 && !visited[nr][nc][1] && crash==0) { visited[nr][nc][1] = true; queue.add(new int[]{nr, nc, 1,min+1}); } if(map[nr][nc]==0 && !visited[nr][nc][crash]){ visited[nr][nc][crash]= true; queue.add(new int[]{nr,nc,crash,min+1}); } } } return -1; } } /* 8 8 01000100 01010100 01010100 01010100 01010100 01010100 01010100 00010100 */

from http://elevensix.tistory.com/98 by ccl(A) rewrite - 2021-10-08 00:27:21