[백준 1194] - 달이 차오른다 가자 -JAVA //le_effort

달이 차오른다, 가자

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	6907	2257	1497	30.030%

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

• 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
• 벽 : 절대 이동할 수 없다. (‘#’)
• 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
• 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
• 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
• 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

예제 입력 1

xxxxxxxxxx
1 7
f0.F..1

예제 출력 1

xxxxxxxxxx
7

예제 입력 2

xxxxxxxxxx
5 5
....1
#1###
.1.#0
....A
.1.#.

예제 출력 2

xxxxxxxxxx
-1

예제 입력 3

xxxxxxxxxx
7 8
a#c#eF.1
.#.#.#..
.#B#D###
0....F.1
C#E#A###
.#.#.#..
d#f#bF.1

예제 출력 3

55

 

 

풀이

비트마스킹 + bfs

 

최근에 비트마스킹 관련 문제만 풀고 있었는데 이 문제를 풀기 위해서였다.

이 문제를 풀기 전 까지 비트마스킹을 아예 단 1도 몰랐고 기본 문제를 차근차근 풀어가며

결국 이 문제를 풀었다.

 

이 문제의 핵심인 어떻게 visited로 한 번 지나갔던 길을 되돌아 갈 것인가?

이걸 해결하는게 포인트이다

f..0.F1

이라고 맵이 있다면 오른쪽으로 쭉 진행하면 가지 못하고

왼쪽으로 가서 f 열쇠를 먹고 다시 오른쪽으로 돌아가 F 문을 열면 돌아 갈 수 있다.

그럼 이걸 어떻게 구현 할 것인가??

 

일단 맨 처음 내 생각은 열쇠는 여러개 있을 수 있으니 출발점 기준으로 가장 가까운 열쇠를 찾으면 되지 않을까? 라고 생각 했었는데 예시를 몇개 그려보니 이는 해당하지 않았다.

 

그냥 visited는 3차원 배열로 설정한다 visited[x좌표] [y좌표] [현재갖고있는열쇠조합]

이렇게 하면 이미 한 번 지나갔던 x,y좌표도 다시 지나 갈 수 있다.

 

전체코드

x
import java.io.*;
import java.util.*;
public class Main {
    static char map[][];
    static int n,m;
    static boolean visited[][][];
    static int dx [] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static int ans = 987654321;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int sx=0;
        int sy= 0;
        String [] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        map = new char[n+1][m+1];
        visited = new boolean [n+1][m+1][1<<6];
        
        
        
        
        
        for(int i=1; i<=n; i++) {
            String tt = br.readLine();
            for(int j=1; j<=m; j++) {
                map[i][j] = tt.charAt(j-1);
                if(map[i][j]== '0') {
                    sx=i;
                    sy=j;
                }
            }
        }
        
        bfs(sx,sy);
        if(ans == 987654321) {
            System.out.println(-1);
        }
        else {
            System.out.println(ans);
        }
    }
    public static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x,y,0,0));
        
        while(!q.isEmpty()) {
            Node a=  q.poll();
            
            
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
​
                if(isRange(nx,ny) && map[nx][ny]!='#' && !visited[nx][ny][a.num]) {
                    if(map[nx][ny]=='1') {
                        ans = Math.min(ans, a.dist+1);
                        continue;
                    }
                    if(map[nx][ny] == '.' || map[nx][ny]=='0') {    // 언제나 갈 수 있는 빈 곳 인 경우
                        visited[nx][ny][a.num] = true;
                        q.add(new Node(nx,ny,a.num,a.dist+1));
                    }
                    if(map[nx][ny]-'a' >=0 && map[nx][ny]-'a'<=5) { // a~f 열쇠인 경우
                        int num = a.num | (1<<(map[nx][ny]-'a'));
                        q.add(new Node(nx,ny,num,a.dist+1));
                        visited[nx][ny][num] = true;
                    }
                    if(map[nx][ny]-'A' >=0 && map[nx][ny]-'A'<=5) {
                        int tmp = map[nx][ny]-'A';
                        if((a.num &(1<<tmp))!=0) {  // 열쇠가 있을 때
                            q.add(new Node(nx,ny,a.num,a.dist+1));
                            visited[nx][ny][a.num] = true;
                        }
                    }
                }
            }
        }
    }
    public static boolean isRange(int x, int y) {
        if(x>=1 && y>=1 && x<=n && y<=m) {
            return true;
        }
        return false;
    }
}
class Node{
    int x,y,num,dist;
    Node(int x, int y,int num, int dist){
        this.x=x;
        this.y=y;
        this.num=num;
        this.dist=dist;
    }
}