[백준] 17090번 미로 탈출하기(java)

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

17090번: 미로 탈출하기

dfs와 dp를 활용한 문제이다.

 

 

핵심

어떠한 발판을 밟는 순간 이후의 동작은 동일해진다. 즉 이후에 탈출을 한다면 그 발판을 밟기 전에도 탈출을 한다는 의미이다.

이러한 사실을 이용해 dp를 적용할 수 있다.

또한 방문했던 곳을 다시 방문한다면 이것은 탈출을 할 수 없다는 의미이다. 이를 활용하여 풀어보자.

 

 

정답 코드

import java.util.Scanner;

public class Main {
    static char[][] map;
    static boolean[][] visited;
    static int n;
    static int m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new char[n][m];
        visited = new boolean[n][m];
        for(int i = 0; i < n; i++) map[i] = sc.next().toCharArray();
        int count = 0;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (dfs(i,j))count++;
            }
        }
        System.out.println(count);
    }

    public static boolean dfs(int y,int x){
        boolean result = false;
        if (0>x|| 0>y ||y>=n ||x>=m)return true;

        if (map[y][x]=='T')return true;
        else if (map[y][x]=='F')return false;

        if (visited[y][x])return false;

        visited[y][x] =true;

        if (map[y][x]=='U')result = dfs(y-1,x);
        else if (map[y][x]=='R') result = dfs(y,x+1);
        else if (map[y][x]=='L') result = dfs(y,x-1);
        else if (map[y][x]=='D') result = dfs(y+1,x);

        map[y][x] = result?'T':'F';
        return result;
    }
}

해설

우선 map에 입력 값을 받는다.

이후 dfs를 각각의 자리별로 시작한다.

만약 범위를 벗어나면 성공으로 간주한다.

또한 성공 시 발판을 T로 만들어준다. 반대의 경우는 F이다.

이미 발판이 T나 F로 바뀐 것은 이미 이후의 결과가 정해진 것을 의미한다.

이미 방문한 곳을 다시 방문한다면 무한 루프를 돌고 있다는 것이므로 false를 반환한다.

 

 

배운 점

이 문제를 보았을 때 한 번에 구현은 못하였지만, 아이디어는 바로 떠올렸다.

아마 문제를 그동안 많이 풀어본 덕분에 사고력이 조금은 늘었다고 느껴졌다.

요즘 알고리즘을 많이 풀고 있는데 아직도 어려운 문제가 많다고  생각된다.

더욱 노력하자