[swexpert] 1226. 미로 1 (bfs, java)

원래 시작점 위치 (2인 곳)을 따로 찾아서 시작점으로 넣어줘야 할 것 같은데 모든 예제의 시작점이 같길래 그냥 (1,1)로 넣어줬다. 만약 다른 테스트 케이스도 돌리는 거라면 시작점도 따로 변수에 담아줘야 할 것이다.

 

D4지만 가장 간단한 bfs예제였다.

끝나는 경우는 3인 곳을 끝까지 만나지 못한 경우를 flag변수의 false로 하여 조건 출력해주면 된다.

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

public class Solution {
	static int t;
	static int[][] map;
	static int[] xpos= {0,0,1,-1};
	static int[] ypos= {1,-1,0,0};
	static boolean[][] vis;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);

		for(int t=1;t<=10;t+=1) {
			sc.nextInt();
			map=new int[16][16];
			vis=new boolean[16][16];
			for (int i = 0; i < 16; i++) {
				String s=sc.next();
				for (int j = 0; j < 16; j++) {
					map[i][j]=s.charAt(j)-'0';
				}
			}
			System.out.printf("#%d ",t);
			bfs();
		}
	}
	private static void bfs() {
		Queue<Integer[]> q=new LinkedList<>();
		q.add(new Integer[] {1,1});
		vis[1][1]=true;
		boolean arrived=false;
		while(q.size()!=0) {
			int y=q.peek()[0];
			int x=q.peek()[1];
			q.poll();
			if(map[y][x]==3) {
				System.out.printf("%d\n",1);
				arrived=true;
				break;
			}
			for (int k = 0; k < 4; k++) {
				int yy=y+ypos[k];
				int xx=x+xpos[k];
				if(xx<0 || yy<0 || xx>=16 || yy>=16)continue;
				if(map[yy][xx]==1)continue;
				if(vis[yy][xx])continue;
				vis[yy][xx]=true;
				q.add(new Integer[] {yy,xx});
			}
		}
		if(!arrived) {
			System.out.printf("%d\n",0);
		}
	}
}