[백준] 17090 미로 탈출하기 🚪 (Java)

문제 링크

문제 설명

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.
어떤 칸(r, c)에 적힌 문자가
U인 경우에는 (r-1, c)로 이동해야 한다.
R인 경우에는 (r, c+1)로 이동해야 한다.
D인 경우에는 (r+1, c)로 이동해야 한다.
L인 경우에는 (r, c-1)로 이동해야 한다.
미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

입력

첫째 줄에 미로의 크기 N, M(3 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.

출력

첫째 줄에 탈출 가능한 칸의 수를 출력한다.

구조화

경계 탈출 가능한지 아닌지 저장하는 int 배열 check를 활용

dfs 탐색 시 경계 탈출 가능하면 재귀로 check[x][y] = 1;

아니면 -1을 저장

 

배열 탐색할 때 check 배열의 값이 초기화 상태인 0이고, 방문하지 않았다면

dfs 탐색 실행

 

check 배열이 1이면 ans++로 갯수를 카운트함

오답 노트

배열 탐색 시 방문 처리 배열(boolean)을 계속 새로 만들어서 시간 초과 뜸

-> 재귀 내에서 false 처리함

 

재귀를 활용하지 않고 list에 갔다온 위치를 담아서 check 배열 값이 바꿔줌

-> 재귀 활용 check[x][y] = dfs(nx, ny);

 

check 배열을 boolean으로 해서 초기화 값이 false라서 경계 탈출 불가능을 false로 저장하면 계속 탐색함

소스 코드

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

public class Main {
    public static int n, m, ans = 0;
    public static boolean[][] v;
    public static int[][] map, check,
            way = {{-1, 0},{0, 1},{1, 0},{0, -1}};
    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());

        map = new int[n][m];
        check = new int[n][m];
        v = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                char c = str.charAt(j);
                switch (c) {
                    case 'U':
                        map[i][j] = 0;
                        break;
                    case 'R':
                        map[i][j] = 1;
                        break;
                    case 'D':
                        map[i][j] = 2;
                        break;
                    case 'L':
                        map[i][j] = 3;
                        break;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (check[i][j] == 0 && !v[i][j]) {
                    if (dfs(i, j) == 1) ans++;
                } else if (check[i][j] == 1) ans++;
            }
        }

        System.out.println(ans);
    }

    public static int dfs(int x, int y) {
        if (x<0 || x>=n || y<0 || y>= m) {
            return 1;
        }
        if (v[x][y]) {
            return -1;
        }
        if (check[x][y]==1) {
            return 1;
        }

        v[x][y] = true;
        int nx = x+way[map[x][y]][0];
        int ny = y+way[map[x][y]][1];

        check[x][y] = dfs(nx, ny);
        v[x][y] = false;

        return check[x][y];
    }
}