[S/W 문제해결 기본] 7일차 - 미로2

미로2

100*100 미로에서 벽 1, 길 0, 출발점 2, 도착점 3 으로 나타낸다.

탈출할 수 있는 미로이면 1, 아니면 2를 출력해라

---

풀이

간단한 bfs 문제이다.

입력을 받을 때 출발점의 좌표를 저장해 놓고 bfs의 출발점으로 큐에 넣어준다.

맵의 크기를 벗어날 때, 이미 방문했을 때, 0일 때 큐에 넣어서 반복한다.

현재 큐의 좌표가 3이라면 ans를 true로 바꿔준다. - (여기서 bfs를 끝내도 될듯)

ans가 true이면 1 false이면 2를 출력해 준다.

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

public class Solution미로2 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for( int tc = 1; tc <= 10; tc++ ) {
			int T = Integer.parseInt(br.readLine());
			int[][] map = new int[100][100];
			
			int startX = 0;
			int startY = 0;
			
			for(int i = 0; i < 100; i++) {
				String str = br.readLine();
				for(int j = 0; j < 100; j++) {
					map[i][j] = str.charAt(j)-'0';
					if(map[i][j] == 2) {
						startX = j;
						startY = i;
					}
				}
			}
			
			ans = false;
			bfs(map, startY, startX);
			
			int result = 1;
			if(!ans) {
				result = 0;
			}
			
			System.out.println("#"+tc+" "+result);
		}
	}
	
	static int[] dy = {0,0,1,-1};
	static int[] dx = {1,-1,0,0};
	static boolean ans;
	
	static void bfs(int[][] map, int y, int x) {
		boolean[][] visited = new boolean[100][100];
		Queue<int[]> queue = new LinkedList<int[]>();
		
		queue.add(new int[] {y,x});
		visited[y][x] = true;
		
		while(!queue.isEmpty()) {
			int[] q = queue.poll();
			
			for(int i = 0; i < 4; i++) {
				int yi = q[0] + dy[i];
				int xi = q[1] + dx[i];
				
				if(yi >= 100 || xi >= 100 || yi < 0 || xi < 0 || visited[yi][xi] )continue;
				
				if(map[yi][xi] == 3) ans = true;
				
				if(map[yi][xi] == 0) {
					visited[yi][xi] = true;
					queue.add(new int[] {yi,xi});					
				}
				
			}
		}
		
	}

}