Categories: SWEA

SWEA 1226 미로1 D4 (자바 Java)

java

SWEA 1226 미로1

문제 정보

문제 링크

문제 출처 : SW Expert Academy
문제 번호 : 1226
문제 제목 : 미로1
문제 난이도 : D4
풀이 언어 : Java

문제

16 x 16 행렬의 형태로 만들어진 미로에서 출발점(2)으로부터 도착지점(3)까지 갈 수 있는 길이 있는지 구하는 문제 (1은 벽, 0은 이동할 수 있는 경로)

접근

깊이 우선 탐색(DFS, Depth-First Search)을 사용해 문제를 해결하였다.

풀이

10개의 테스트 케이스에 대해 반복합니다.
16×16 크기의 미로와 방문 여부를 확인하기 위한 boolean 배열을 초기화합니다.
테스트 케이스 번호를 입력 받고, 16줄에 걸쳐 미로 정보를 입력 받습니다. 각 줄은 String으로 받은 후, 각 문자를 숫자로 변환하여 미로 배열에 저장합니다.
dfs 함수를 호출하여 시작점(1,1)에서 출발하여 미로 탐색을 시작합니다.
현재 위치가 미로 범위를 벗어나거나 벽(1)이거나 이미 방문한 경우, 0을 반환하여 더 이상 탐색하지 않습니다.
현재 위치가 출구(3)인 경우, 1을 반환하여 탐색을 성공적으로 마칩니다.
현재 위치는 방문한 것으로 표시합니다.
현재 위치에서 상하좌우 네 방향으로 재귀적으로 dfs를 호출합니다. 이 중 한 방향에서 출구를 찾으면(반환값이 1이면) 1을 반환하여 탐색을 중단합니다.
모든 방향에서 출구를 찾지 못하면 0을 반환합니다.
각 테스트 케이스에 대해 DFS 탐색 결과(출구 도달 가능 여부)를 출력합니다.

후기

DFS 문제에 더 적응하기 위해 많은 문제를 풀어봐야겠다.

코드

Java

import java.util.Scanner;
import java.io.FileInputStream;
 
class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
 
        for(int test_case = 1; test_case <= 10; test_case++)
        {
            int[][] maze = new int[16][16];
            boolean[][] visited = new boolean[16][16];
            int t = sc.nextInt();
 
            for (int i = 0; i < 16; i++) {
                String line = sc.next();
                for (int j = 0; j < 16; j++) {
                    maze[i][j] = line.charAt(j) - '0';
                }
            }
            System.out.println("#" + test_case + " " + dfs(maze, visited, 1, 1));
        }
    }
        private static int dfs(int[][] maze, boolean[][] visited, int x, int y) {
        if (x < 0 || y < 0 || x >= 16 || y >= 16 || maze[x][y] == 1 || visited[x][y]) {
            return 0;
        }
        
        if (maze[x][y] == 3) {
            return 1;
        }
        
        visited[x][y] = true;
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
 
        for (int i = 0; i < 4; i++) {
            if (dfs(maze, visited, x + dx[i], y + dy[i]) == 1) {
                return 1;
            }
        }
        return 0;
    }
}