백준_17090_미로탈출하기

https://www.acmicpc.net/problem/17090

17090번: 미로 탈출하기

 

문제 해석

1. NxM 미로가 있다.
2. U, R, D, L 명령에 따라 이동한다.
3. 탈출 가능한 칸을 Count 해준다.
   1. 탈출 가능이란 : 그 칸에서 이동을 시작해서 칸에 적힌대로 이동 했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

풀이

• DFS를 이용해서 푼다. 
• 방문 처리가 중요하다.
  • 처음 방문 한 곳이면서 탈출 가능하면 Count++해준다.
  • 처음 방문 한 곳이 아니면 카운트 해주지 않는다. 즉, 이미 탈출 가능한 경로를 계속해서 저장해야 한다.(DP)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[][] map, visited;
    static boolean[] successCheck;
    static int N, M, num = 1, ans = 0;
    static int[][] dt = {{-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];
        visited = new int[N][M];
        successCheck = new boolean[N * M + 1];
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                char c = input.charAt(j);
                if (c == 'U') map[i][j] = 0;
                else if (c == 'R') map[i][j] = 1;
                else if (c == 'D') map[i][j] = 2;
                else map[i][j] = 3;
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visited[i][j] != 0) continue;
                dfs(i, j, 0);
                num++;
            }
        }

        System.out.println(ans);
        br.close();
    }

    public static void dfs(int x, int y, int count) {
		//만약 처음 탈출했다면.
        if (check(x, y)) {
            successCheck[num] = true;
            ans += count;
            return;
        //만약 처음 탈출이 아니라면
        } else if (visited[x][y] != 0) {
            if (successCheck[visited[x][y]]) {
                successCheck[num] = true;
                ans += count;
            }
            return;
        }

        visited[x][y] = num; //visit 체크해주기
        dfs(x + dt[map[x][y]][0],  y + dt[map[x][y]][1], count + 1); // 방향 별로 넣어주기
    }

	//탈출조건 체크
    public static boolean check(int x, int y) {
        return x < 0 || x >= N || y < 0 || y >= M;
    }
}