백준 - 17090 미로 탈출하기(Java)

17090 미로 탈출하기

문제 설명

요구사항

1. U (x-1, y) 좌
2. R (x,y+1) 상
3. D (x+1,y) 우
4. L (x,y-1) 하
5. 미로의 경계 밖으로 이동한다면 탈출

접근 방식

1. 탈출 가능한 모든 칸의 수를 구하기 위해 각 칸마다 DFS를 수행하여 지시된 방향을 따라 이동합니다.
2. 탐색 중 같은 칸을 다시 방문하면 사이클 → 탈출 실패.
3. check 배열로 사이클 여부를 추적, visited 배열로 이미 판정된 경로를 재사용.

• 첫 시도에서는 경로 결과를 저장하지 않아 모든 칸을 매번 탐색하여 시간 초과가 발생했습니다. 이를 해결하기 위해 메모이제이션 방법을 사용해 visited 배열을 추가했습니다.

코드 설명

import java.io.;
import java.util.;

public class Main{
static char[][] arr;
static int[][] check;
static boolean[][] visited;
static int n, m, answer = 0;

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new char[n][m];
check = new int[n][m];
visited = new boolean[n][m];

for(int i=0; i<n; i++){
String line = br.readLine();
for(int j=0; j<m; j++){
arr[i][j] = line.charAt(j);
}
}

for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(DFS(i, j)) answer++;
}
}
System.out.println(answer);
}

static boolean DFS(int r, int c){
if(r<0 || r>=n || c<0 || c>=m) return true; // 탈출 성공

if(visited[r][c]) return true;
if(check[r][c] == 1) return false; // 사이클

check[r][c] = 1; // 탐색 중 표시
boolean flag;
if(arr[r][c] == 'U') flag = DFS(r-1, c);
else if(arr[r][c] == 'R') flag = DFS(r, c+1);
else if(arr[r][c] == 'D') flag = DFS(r+1, c);
else flag = DFS(r, c-1);
check[r][c] = 0;

if(flag) visited[r][c] = true;
return flag;
}
}

복잡도 분석

• 시간 복잡도: O(N × M) (각 칸을 최대 한 번만 탐색)
• 공간 복잡도: O(N × M) (배열 3개 사용)

느낀점

이 문제를 통해 DFS에서 사이클 처리와 메모제이션의 중요함을 다시 느꼈습니다. 특히, 단순 탐색은 시간초과로 이어지기 때문에 메모제이션을 이용하여 이미 계산된 결과를 저장하는 습관이 알고리즘을 구현하는데 매우 효과적이며 필수라는 것을 다시 느끼게 되었습니다.