[SWEA] 1226. [S/W 문제해결 기본] Queue - 미로1

문제

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE

SW Expert Academy

 

 

풀이

이 문제는 전형적인 DFS 문제이다. 방문 배열을 이용하지 않고 구현한다면 여지없이 스택 오버플로우가 발생한다. 방문 배열을 별도로 이용해서 해당 경로에서 방문했었던 지점은 다시 가지 않도록 해준다.

 

import java.util.*;
 
public class Solution {
    static Scanner scan = new Scanner(System.in);
    static String[] map = new String[16];
    static boolean[][] visited = new boolean[16][16];
    static int chk = 0;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };
    static int sr, sc;
 
    static void reset_visited() {//방문 여부 배열 초기화
        for(int i=0;i<16;i++) {
            for(int j=0;j<16;j++)
                visited[i][j] =false;
        }
    }
    
    static void make_map() {
        for (int i = 0; i < 16; i++) {
            map[i] = scan.next();
            for(int j=0;j<16;j++) {
                if(map[i].charAt(j) == '2') {//시작점 찾기
                    sr = i;
                    sc = j;
                }
            }
        }
    }
 
    static boolean is_valid(int r, int c) {//유효성 검사
        if ((r >= 0 && r < 16) && (c >= 0 && c < 16) && map[r].charAt(c) != '1')
            return true;
        return false;
    }
 
    static void dfs(int r, int c) {
        if (map[r].charAt(c) == '3') {
            chk = 1;
            return;
        }
        for (int i = 0; i < 4; i++) {//상하좌우 체크
            if (is_valid(r + dr[i], c + dc[i]) && !visited[r + dr[i]][c + dc[i]]) {
                visited[r + dr[i]][c + dc[i]] = true;
                dfs(r + dr[i], c + dc[i]);
                visited[r + dr[i]][c + dc[i]] = false;
            }
                
        }
    }
 
    static void solution() {
        for (int i = 1; i <= 10; i++) {
            scan.nextInt();
            make_map();
            dfs(sr, sc);
            System.out.println("#" + i + " " + chk);
            chk = 0;
            reset_visited();
        }
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        solution();
    }
}