2178 - 미로찾기 (BFS)

---

순서도 작성

 

 

 

소스

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//백준
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int depth = sc.nextInt();
		int wide = sc.nextInt();

		int[][] array = new int[depth][wide];

		boolean[][] visited = new boolean[depth][wide];
		Queue<int[]> q = new LinkedList<>();

		int x, y, count, result=Integer.MAX_VALUE;

		for (int i = 0; i < depth; i++) {
			String[] str = sc.next().split("");
			for (int j = 0; j < wide; j++) {
				array[i][j] = Integer.parseInt(str[j]);
			}
		}

		// 초기값
		q.offer(new int[] { 0, 0, 1 });

		while (!q.isEmpty()) {
			int[] point = q.poll();
			x = point[0];
			y = point[1];
			count = point[2];
		//	System.out.println(x+","+y+" "+count);
			if(x==depth-1&&y==wide-1) {
				if(result>count)
					result=count;
			}

			if (array[x][y] == 0) {

			} else if (array[x][y] == 1 && visited[x][y]==false) {
				
				
				if(x>0) {//상
					q.offer(new int[] {x-1,y,count+1});
				}
				if(x<depth-1) {//하
					q.offer(new int[] {x+1,y,count+1});
				}
				if(y>0) {//좌
					q.offer(new int[] {x,y-1,count+1});
				}
				if(y<wide-1) {//우
					q.offer(new int[] {x,y+1,count+1});
				}
				
				
				
				visited[x][y]=true;
				
			}
		}System.out.println(result);

	}

}

좌표값과 이동값을 같이 큐에 넣어주면서 이동 가능한 경로를 탐색했다.

조건에 방문여부와 0/1 체크를 했보았지만 속도와 메모리 차이가 별로 없었다.