1226. 미로1

SW Expert 1226. 미로1

* 문제의 저작권은 SW Expert에 있습니다.

[문제 접근]

BFS로 접근

시작점을 먼저 찾아 큐에 넣기

넣은 후 방문 여부 체크 -> 방문하지 않았을 경우 -> 4방향에 길이 있는지 확인 -> 길이 있다면 큐에 넣음 -> 다시 방문 여부 체크를 반복

방문했으면 다시 큐를 꺼내서 방문 여부 체크

[코드]

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Solution_1226 {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
 
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int test_case = 1; test_case <=10; test_case++) {
            br.readLine();
            int[][] map = new int[16][16]; //지도
            boolean[][] visit = new boolean[16][16]; //방문 체크
 
            String str = "";
            for (int i = 0; i < 16; i++) {
                str = br.readLine();
                for (int j = 0; j < 16; j++) {
                    map[i][j] = Integer.parseInt(str.charAt(j)+"");
                }
            }
 
            int result = 0;
            Queue<Cord> queue = new LinkedList<>();
            for (int i = 0; i < 16; i++) {
                for (int j = 0; j < 16; j++) {
                    if (map[i][j] == 2) { //시작점이면
                        queue.offer(new Cord(i, j)); //큐에 넣는다
 
                        while (!queue.isEmpty()) {// 큐가 비지 않았다면
                            Cord temp = queue.poll(); //꺼낸다
 
                            if (visit[temp.x][temp.y]) { //이 좌표를 방문했다면
                                continue; //계속 진행
                            }
 
                            //방문하지 않았다면
                            visit[temp.x][temp.y] = true;
 
                            for (int k = 0; k < 4; k++) { //4방향 검사
                                int nx = temp.x + dx[k]; //다음 x의 좌표
                                int ny = temp.y + dy[k]; //다음 y의 좌표
 
                                //다음 x,y의 좌표 값이 범위를 넘지 않고 방문하지 않았을 경우
                                if (nx < 16 && ny < 16 && nx >0 && ny>0 && !visit[nx][ny]) {
                                    if (map[nx][ny] == 0) { //길이 있다면 좌표 값 넣고 다시 반복
                                        queue.offer(new Cord(nx, ny));
                                    } else if (map[nx][ny] == 3) { //출구가 있다면
                                        result = 1;
                                    }
                                }
                            }
                        }
                    }
                }
            }
 
            System.out.println("#"+test_case + " " + result);
        }
    }
 
    static class Cord{
        int x;
        int y;
 
        public Cord(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
 
    }
}