[SW Expert] 1226. [S/W 문제해결 기본] 7일차 - 미로1

1) 생각

미로가 주어진다 출발점은 2, 도착점은 3으로 표현되어 있을 때, 도착점까지 갈 수 있는지를 판단하여라.

처음 생각

미로 탐색이므로 BFS를 통해서 풀이를 하였다.

다음 생각

16 x 16으로 크기가 작게 정해져 있으므로 DFS를 이용해 풀어도 빠르게 풀릴 것 같다.

2) 방안

1) BFS를 사용해서 풀이를 하였다.

▶x와 y의 좌표를 class를 따로 만들어 사용하지 않고 Queue 2번 넣어줘서 풀이를 해보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Solution {
    static int[][] arr;
    static int sx,sy;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        int tc = 10;
        for(int i=1;i<=tc;i++) {
            br.readLine();
            arr = new int[16][16];
            for(int j=0;j<16;j++) {
                String t = br.readLine();
                for(int k=0;k<16;k++) {
                    arr[j][k] = t.charAt(k)-'0';
                    if(arr[j][k]==2) {
                        sx = j;
                        sy = k;
                    }
                }
            }
            sb.append("#"+i+" ");
            solve();
        }
        System.out.print(sb);
    }
    
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static void solve() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(sx);
        queue.add(sy);
        while(!queue.isEmpty()) {
            int x = queue.poll();
            int y = queue.poll();
            for(int i=0;i<4;i++) {
                int tx = x+dir[i][0];
                int ty = y+dir[i][1];
                if(arr[tx][ty]!=1) {
                    if(arr[tx][ty]==3) {
                        sb.append("1\n");
                        return;
                    }
                    arr[tx][ty] = 1;
                    queue.add(tx);
                    queue.add(ty);
                }                
            }            
        }
        sb.append("0\n");
    }
}