미로 탐색

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

2178번: 미로 탐색

// 코드

import java.util.*;
import java.io.*;
 
public class Main{  
  
  // 상, 하, 좌, 우 
  static int[][] dir  = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  
  static int N, M;
  static int[][] arr;
  static int[][] result;
  
  static void BFS() {
    
    Deque<int[]> deq = new ArrayDeque<>();
    deq.add(new int[]{0, 0});
    int cnt = 1;
    result[0][0] = cnt++;
    
    while(!deq.isEmpty()) {
      int[] getV = deq.pop();
      
      for(int i=0; i<4; i++) {
        // 상, 하, 좌, 우
        int ny = dir[i][0] + getV[0];
        int nx = dir[i][1] + getV[1];
        
        if((0 <= ny && ny < N) && (0 <= nx && nx < M) && (result[ny][nx] == 0) && (arr[ny][nx] == 1)) {
          result[ny][nx] = Math.max(result[getV[0]][nx], result[ny][getV[1]]) + 1;
          deq.add(new int[]{ny, nx});
        }
        
      }
    }
    
  }
  
  // main
  public static void main(String[] args) throws Exception {
    
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    
    arr    = new int[N][M];
    result = new int[N][M];
    
    for(int i=0; i<N; i++) {
      arr[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
    }
    
    BFS(); 
     
    bw.write(String.valueOf(result[N-1][M-1]));
    br.close();
    bw.flush();
    bw.close();
  }
}

 

// 복습

import java.util.*;
import java.io.*; 
 
 
public class Main {   
  
  static final int[][] DELTAS = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
  static int N, M;
  static int[][] arr, visited;
  
  
  // main  
  public static void main( String[] args ) throws Exception {
    
    // Please Enter Your Code Here 
    BufferedWriter bw  = new BufferedWriter( new OutputStreamWriter( System.out ) );
    BufferedReader br  = new BufferedReader( new InputStreamReader( System.in ) );
    StringTokenizer st = new StringTokenizer( br.readLine() );
    
    N = Integer.parseInt( st.nextToken() );
    M = Integer.parseInt( st.nextToken() );
    
    arr     = new int[N][M];
    visited = new int[N][M];
    
    for ( int i = 0; i < N; ++i ) {
      String getStr = br.readLine(); 
      for ( int j = 0; j < M; ++j ) arr[i][j] = Integer.parseInt( String.valueOf( getStr.charAt(j) ) );
    } 
    
    bfs();
    
    int ret = visited[N-1][M-1] + 1;
    bw.write( String.valueOf(ret) );
    
    bw.flush();
    bw.close();
    br.close(); 
  }
  
  
  public static void bfs() {
    
    Deque< int[] > deq = new ArrayDeque<>();
    deq.offer( new int[] { 0, 0 } );
    
    while ( !deq.isEmpty() ) {
      
      int[] pos = deq.poll();
      int posY = pos[0], posX = pos[1];
      
      for ( int dir = 0; dir < 4; ++dir ) {
        
        int ny = posY + DELTAS[dir][0], nx = posX + DELTAS[dir][1];
        if ( ny < 0 || ny >= N || nx < 0 || nx >= M || ( ny == 0 && nx == 0 ) || arr[ny][nx] == 0 || visited[ny][nx] != 0 ) continue;
        
        deq.offer( new int[] { ny, nx } );
        visited[ny][nx] = visited[posY][posX] + 1;
        
      }
      
    }
    
  }
  
    
}