백준 : 1194

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

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

문제를 풀때 A~Z 까진줄 알고 어떻게 풀어야할지 많이 고민을 했었다.

그런데 A-F 까지인것을 발견 flag 1<<6 크기를 할당하여서 000000 ~ 111111 까지의 flag 정보를 boolean형 배열에 선언할수가 있다.

flag는 현재 내가 가지고있는 키의 정보이다 1이면 key를 가지고 있는 0이면 가지고 있지 않는 것으로 표현한다.

이렇게 Q에 위치정보 + key정보를 넘기고 visit[ny][nx][flag] 정보를 이용해서 이미 지나간 곳인지 아닌지 확인 할수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class B1194 {
    static int N, M;
    static char map[][];
    static boolean visit[][][];
    static int dy[] = { 1, -1, 0, 0 };
    static int dx[] = { 0, 0, 1, -1 };
 
    static class Moon {
        int y;
        int x;
        int flag;
 
        public Moon(int y, int x, int flag) {
            this.y = y;
            this.x = x;
            this.flag = flag;
        }
    }
 
    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 char[N][M];
        visit = new boolean[N][M][2 << 6];
        Queue<Moon> q = new LinkedList<Moon>();
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if (map[i][j] == '0') {
                    visit[i][j][0] = true;
                    q.add(new Moon(i, j, 0));
                }
            }
        }
 
        int time = 0;
        int Answer = -1;
 
        while (!q.isEmpty()) {
 
            int size = q.size();
 
            for (int s = 0; s < size; s++) {
                Moon tmp = q.poll();
 
                if (map[tmp.y][tmp.x] == '1') {
                    Answer = time;
                    break;
                }
 
                for (int d = 0; d < 4; d++) {
                    int ny = tmp.y + dy[d];
                    int nx = tmp.x + dx[d];
 
                    if (ny < 0 || nx < 0 || ny >= N || nx >= M)
                        continue;
                    if (map[ny][nx] == '#')
                        continue;
                    if (visit[ny][nx][tmp.flag])
                        continue;
                    if (map[ny][nx] >= 'a' && map[ny][nx] <= 'f') {
                        // 키를 획득 할때
                        visit[ny][nx][tmp.flag | (1 << (map[ny][nx] - 'a'))] = true;
                        q.add(new Moon(ny, nx, tmp.flag | (1 << (map[ny][nx] - 'a'))));
                    } else if (map[ny][nx] >= 'A' && map[ny][nx] <= 'F') {
                        // 문을 만낫을 때
                        if((tmp.flag &(1<<map[ny][nx]-'A')) == (1<<map[ny][nx]-'A')) {
                            visit[ny][nx][tmp.flag] = true;
                            q.add(new Moon(ny,nx,tmp.flag));
                        }
                    } else {
                        // . 일때
                        visit[ny][nx][tmp.flag] =true;
                        q.add(new Moon(ny, nx, tmp.flag));
                    }
 
                }
 
            }
            if (Answer != -1) {
                break;
            }
            time++;
 
        }
 
        System.out.println(Answer);
    }
 
}