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

import java.util.Scanner;

 

 

class Solution {

    static int Answer;

 

    static int[][] map = new int[16][16]; // 행, 열

    static int[][] visited = new int[16][16]; // 행, 열

    static boolean findPath ;

     

    public static void main(String args[]) throws Exception {

         

         

        Scanner sc = new Scanner(System.in);

         

        for(int T=1; T <=10; T++) {

             

            // Test 번호

            sc.nextLine(); 

            int startX = -1, startY = -1;

             

            //map에 데이터 입력

            for(int i=0; i<16; i++) { // 행(y)

                String rowInput = sc.nextLine();

                for(int j=0; j<16; j++) { // 열(x)

                    // j => x , i => y

                    map[i][j] = rowInput.charAt(j) - '0';

                    visited[i][j] = 0;

                    if(map[i][j] == 2) {

                        startY = i;

                        startX = j;

                    }

                }

            }

             

            findPath = false;

            findView(startY, startX);

             

            System.out.println(String.format("#%d %d", T, findPath ? 1:0));

        }

         

    }

     

    public static void findView(int y, int x) {

        // 1, -1이 겹치지 않게 방향설정 (왼쪽, 아랫쪽, 오른쪽, 위쪽)

        int[] rotX = {-1,0,1,0};

        int[] rotY = {0,1,0,-1};

         

        // 도킹

        visited[y][x] = 1;

        int newX, newY;

        for(int i=0; i<4; i++) {

            // 왼쪽, 아랫쪽, 오른쪽, 위쪽을 우선순위로 탐색

            newX = x + rotX[i];

            newY = y + rotY[i];

            if(isWay(newY, newX)) { // 길이 있는 경우면 전진

                 

                // 도중에 출구를 발견한 경우

                if(map[newY][newX]==3) {

                    findPath = true;

                    break;

                }

                 

                findView(newY, newX); // 무한 재귀호출

            }

        }

        // 도킹 해제

        visited[y][x] = 0;

    }

     

    public static boolean isWay(int y, int x) {

        if(x<0 || x>15 || y<0 || y>15) { // 배열 범위를 넘어서는 경우

            return false;

        }else if(visited[y][x]==1){ // 지나온 곳은 통과할 수 없다.

            return false;

        }else if(map[y][x]==1) { // 벽은 통과할 수 없다.

            return false;

        }else if(findPath) {

            // 이미 길을 찾은 경우 break point 재귀함수를 모두 종류하기 위하여

            return false;

        }

        return true;

    }

     

}