[SWEA 1227] 미로2 (JAVA)

문제

- 100*100 행렬의 형태로 만들어진 미로에서 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 문제

- 1은 벽, 0은 길 2는 출발점, 3은 도착점

 

풀이방법

- DFS알고리즘을 이용

- 상, 하, 좌, 우로 이동하여 출발지점에서 도착지점까지 갈 수 있는지 판단

- 만약 도착지점에 도달했을 경우 리턴

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Solution_D4_1227_미로2 {
    static StringBuilder sb = new StringBuilder();
    static int [][] map;
    static boolean[][] visited;
    static int startX, startY,find;
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
 
    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 N = Integer.parseInt(br.readLine());
            
            map = new int[100][100];
            visited = new boolean[100][100];
            
            for(int i=0;i<100;i++) {
                String str = br.readLine();
                for(int j=0;j<100;j++) {
                    map[i][j]=str.charAt(j)-48;
                    if(map[i][j]==2) {
                        startX = i; startY = j;
                    }
                }
            }
            find=0;
            sb.append("#"+N+" ");
            dfs(startX, startY);
            sb.append(find+"\n");
            
        }
        System.out.println(sb.toString());
 
    }
    
    public static void dfs(int x, int y) {
        if(find==1) return;
        visited[x][y] = true;
        
        for(int i=0;i<4;i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(map[nx][ny]==3) {
                find=1;
                return;
            }
            
            if(check(nx,ny) && !visited[nx][ny] && (map[nx][ny]==0)) {
                dfs(nx,ny);
            }
        }    
    }
    
    public static boolean check(int x, int y) {
        return x>=0 && y>=0 && x<100 && y<100;
    }
 
}