백준 : 2178 (미로탐색) (BFS)

이번 문제는 행렬을 이용한 기본적인 BFS문제인거 같다.

 

여기서 주의할 점은 크게 없지만,

방문 그래프, 거리 그래프, 입력값 그래프 이렇게 세개의 그래프를 이용한다는 점만 주의하면 될거 같다.

import java.util.*;

class Node{
	private int x;
	private int y;
	
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	public int getX() {
		return this.x;
	}
	
	public int getY() {
		return this.y;
	}
}

class Main{
	
	static int n,m;
	static boolean[][] visited;
	static int[][] dist;
	static int[][] graph;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	
	public static void bfs(int x, int y) {
		Queue<Node> q = new LinkedList<Node>();
		q.offer(new Node(x ,y)); //삽입
		visited[x][y] = true;  //방문표시
		dist[x][y] = 1; //거리체크
		
		while(!q.isEmpty()) {
			Node nowNode = q.poll();
			x = nowNode.getX();
			y = nowNode.getY();
			
			for(int i=0; i<4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx <0 || nx >=n || ny <0 || ny >=m) //범위
					continue;
				
				if(visited[nx][ny] == false && graph[nx][ny] ==1) { //지나갈 수 있는길
					visited[nx][ny] = true; //방문표시
					dist[nx][ny] = dist[x][y] +1; //거리체크
					q.offer(new Node(nx, ny)); //삽입
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		sc.nextLine(); //버퍼
		
		//초기화
		visited = new boolean[n][m]; //인덱스 0부터 시작
		dist = new int[n][m];
		graph = new int[n][m];
		
		//그래프 입력
		for(int i=0; i<n; i++) { //인덱스 0부터 시작
			String st = sc.nextLine();
			String[] stArr = st.split("");
			for(int j=0; j<m; j++) {
				graph[i][j] = Integer.parseInt(stArr[j]);
			}
		}
		
		bfs(0,0);
		
		System.out.println(dist[n-1][m-1]);
	}
}