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;
}
}