[BOJ]1194번 : 달이 차오른다, 가자.

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

1194번: 달이 차오른다, 가자.

 

 

분류 : BFS

 

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

class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {
    public static PrintWriter out;
    static final int inf = Integer.MAX_VALUE / 2;
    static int N, K, M;
    static boolean[][][] visited;
    static char[][] map;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        N = sc.nextInt();
        M = sc.nextInt();
        map = new char[55][55];
        visited = new boolean[55][55][65];
        Queue<Point> q = new LinkedList<Point>();

        for (int r = 0; r < N; r++)
            map[r] = sc.next().toCharArray();

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                if (map[r][c] == '0') {
                    q.offer(new Point(r, c,0));
                }
            }
        }

        int result = bfs(q);
        if (result == -1) {
            out.println(-1);
        } else {
            out.println(result);
        }
        out.flush();
    }

    private static int bfs(Queue<Point> q)
    {
        visited[q.peek().x][q.peek().y][0]=true;
        int Hour = 0;
        while (!q.isEmpty())
        {
            int size = q.size();
            for (int sz = 0; sz < size; sz++)
            {
                Point p = q.poll();
                int x = p.x;
                int y = p.y;
                int key = p.key;
                if (map[x][y] == '1') {
                    return Hour;
                }

                for (int ar = 0; ar < 4; ar++) {
                    int cx = x + dx[ar];
                    int cy = y + dy[ar];
                    int ckey = key;
                    if (cx < 0 || cy < 0 || cx >= N || cy >= M || map[cx][cy] == '#')
                        continue;

                    if(map[cx][cy] == '#') continue;
                    
                    if(map[cx][cy] >= 'a' && map[cx][cy] <= 'f'){
                        ckey |= (1 <<(map[cx][cy]-'a'));
                    }
                    if(map[cx][cy] >= 'A' && map[cx][cy] <= 'F'){
                        if((ckey & (1 << (map[cx][cy]-'A')))==0) continue;
                    }
                    if(visited[cx][cy][key]) continue;
                    visited[cx][cy][ckey] = true;
                    q.offer(new Point(cx,cy,ckey));
                }
            }
            Hour++;
        }
        return -1;
    }
}

class Point {
    int x;
    int y;
    int key;
    Point(int x, int y,int key) {
        this.x = x;
        this.y = y;
        this.key = key;
    }
}

 

문제만 읽고서 처음에는 BFS를 돌리면서 소문자일 경우 -> List에 add 하고 대문자일 경우 -> List에 contain 있는지 판단해서

출구까지 걸리는 시간을 계산 하는 식으로 했더니 시간 초과가 뜨면서 실패

어떻게 하지 고민중에 비트 마스크를 이용하라는 힌트를 얻었고 BFS+비트 마스크를 활용하여 통과 완료.

되게 도움이 많이 되고 활용도가 높아질수 있는 지식을 얻은 것 같다.