<백준> 2206번 자바 알고리즘[BFS]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main
{
    static class Loc{
        int i; // 가로
        int j; // 세로 
        int dis;
        boolean des;
        
        public Loc(int i, int j, int dis, boolean des){
            this.i = i;
            this.j = j;
            this.dis = dis;
            this.des = des;
        }
    }

	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        
		int n = Integer.parseInt(inputs[0]);
		int m = Integer.parseInt(inputs[1]);
		   
		char[][] map = new char[n][m];
		for (int i = 0; i < n; i++){
		    String input = br.readLine();
		    for(int j = 0; j < m; j++){
		        // 내용 입력 
		        // 한 글자 씩 추가 
		        map[i][j] = input.charAt(j);
		        
		    }
		    
		}
		// 초기화
		Queue<Loc> q = new LinkedList<>();
		q.add(new Loc(0,0,1,false));
		int[] dx = {0, 0, 1, -1};
		int[] dy = {-1, 1, 0, 0};
		
		// 방문 했는지 안했는지 => 최소
		boolean[][][] visited = new boolean[n][m][2];
		
		
		// queue 빌 때 까지 
		while(!q.isEmpty()){
		    // 제일 앞의 queue 가져오기 
		    Loc now = q.poll();
		    
		    // 도착했을 때 
		    if(now.i == m - 1 && now.j == n - 1){
		        System.out.println(now.dis);
		        return;
		        
		    }
		    
		    // 상하좌우 
		    
		    for(int d=0; d < 4; d++){
		        int nx = now.i + dx[d];
		        int ny = now.j + dy[d]; 
		        // 범위 밖 일 때 
		        if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
		        
		        if(map[ny][nx] == '0'){
		            if(!now.des && !visited[ny][nx][0]){
		                q.add(new Loc(nx, ny, now.dis + 1, false));
		                visited[ny][nx][0] = true;
		            }else if(now.des && !visited[ny][nx][1]){
		                q.add(new Loc(nx, ny, now.dis + 1, true));
		                visited[ny][nx][1] = true;
		            }
		        }else if (map[ny][nx] == '1'){
		            if(!now.des){
		                q.add(new Loc(nx, ny, now.dis + 1, true));
		                visited[ny][nx][1] = true;
		            }
		        }
		    }
		}
		
		// 그냥 끝났을 때 
		System.out.println(-1);
		
		
		
	}
}

며칠동안 계속 생각했다.

 

아직 bfs 개념이 확실히 잡혀 있지 않아서 더더욱 헷갈리는 것 같다.

 

 

메모로 생각 적은 것들 

---

 

전에 푼 문제들은 visited가 1개만 있어도 가능했음

이젠 visited가 2개 있어야 됨 => 두가지 case 로 나뉘므로(1번 부쉈냐, 한번도 안부쉈냐)

visited[][][0] 한번도 안 부숨 
visited[][][1] 한번 부숨 

벽이 아닐 때 
    부순적x -> 코드 입력
        q에 넣음
        vistied 반영 
    부순적o -> 코드 입력 
        q에 넣음
        vistied 반영

벽 일때 
    부순적x -> 코드 입력 
         q에 넣음
        vistied 반영