https://www.acmicpc.net/problem/1194
1194번: 달이 차오른다, 가자.
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,
www.acmicpc.net
분류 : 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+비트 마스크를 활용하여 통과 완료.
되게 도움이 많이 되고 활용도가 높아질수 있는 지식을 얻은 것 같다.
'PS' 카테고리의 다른 글
[BOJ]2206번 : 벽 부수고 이동하기 (0) | 2017.04.02 |
---|---|
[BOJ]3055번: 탈출 (0) | 2017.04.02 |
[BOJ]5427번 : 불 (0) | 2017.03.31 |
[BOJ]4179번 : Fire! (0) | 2017.03.31 |
[BOJ]7569번 : 토마토 (0) | 2017.03.29 |