자바로 백준 2178 풀기

풀이)

미로에서 인접한 칸으로만 이동하니 BFS를 사용한다.
입력 크기가 100이하라서 인접 행렬을 통해 그래프를 표현한다.
인접 행렬은 시간 복잡도가 O(n^2)
인접 리스트는 시간 복잡도가 O(n+e)

배열에서 동서남북 움직이는 법
배열에선 -x가 위 +x가 아래 -y가 좌 +y가 우다.
상 하 좌 우
dx = {-1, 1, 0, 0}
dy = {0, 0, -1, 1}

내 코드)

// 백준 온라인 저지 2178번

import java.io.*;
import java.util.*;

public class Main{

	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static boolean visited[][];
	static int A[][];
	static int N, M;
	
	static void BFS(int a, int b) {
		Queue<int[]> queue = new LinkedList<>();
		// 큐에 맨 처음 시작점 넣는다.
		queue.offer(new int[] {a, b});
		while(!queue.isEmpty()) {
			//now는 지금 있는 위치를 말함. 
			int now[] = queue.poll();
			visited[a][b] = true;
			for(int k=0;k<4;k++) {
				//상하좌우 갈 수 있는 곳을 탐색한다.
				//현재 위치 now에서 갈 수 있는 좌표 탐색,
				//now 위치가 (2,3) 이라면 
				//x, y = (1,3) (3,3) (2,2) (2,4) 이렇게 인접 위치가 나옴.
				int x = now[0] + dx[k];
				int y = now[1] + dy[k];
				if(x >= 0 && y>=0 && x<N && y<M) {
					//(x,y)가 유효 위치라면 만약 A[x][y]가 0이 아니라면 갈 수 있는 위치.					
					if(A[x][y]!=0 && !visited[x][y]) {
						visited[x][y] = true;
						A[x][y] = A[now[0]][now[1]] + 1;
						queue.add(new int[] {x, y});
					}
				}
			}
		}
	}
	
	public static void main(String[]args) throws IOException{
		
		// 입력. 
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		A = new int[N][M];
		visited = new boolean[N][M];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(bf.readLine());
			String str = st.nextToken();
			for(int j=0;j<M;j++) {
				A[i][j] = Integer.parseInt(str.substring(j, j+1));
			}
		}
		BFS(0,0);
		System.out.println(A[N-1][M-1]);
	}
}