반응형
11-11 07:25
- Today
- Total
Link
개발하는 고라니
[백준] 17244번 : 아맞다우산 본문
반응형
[BFS + 비트마스크]
N x M 격자 맵에서 'X'로 표시된 모든 물건을 챙기고 탈출구 'E'로 최소한의 움직임으로 나가는 방법을 찾는 문제. 격자의 크기 제한이 최대 50x50이고 물건의 개수가 최대 5개라서 비트마스킹을 안써도 메모리적인 부분에서 큰 손실은 없을 것 같으나, 물건이 모두 'X'로 동일하여 현재 내가 특정 정점에 방문했을 때, 어떤 물건을 갖고 있는 지를 체크하는 것이 비트마스킹만큼 좋은 것이 없기에 비트마스킹을 사용했다.
먼저 입력을 받을 때 'X'인 곳을 '0', '1', '2', ...처럼 X가 아닌 숫자로 지정해놓는다. 이는 물건에 "인덱스"를 부여하는 효과를 가져오며 물건이 몇 개 존재하는지 또한 알아낼 수 있다.
int sY = 0, sX = 0;
char idx = '0';
for(int i=1; i<=n; i++) {
char[] str = br.readLine().toCharArray();
for (int j = 1; j <= m; j++) {
map[i][j] = str[j - 1];
if (map[i][j] == 'X') {
map[i][j] = idx++;
k++;
} else if (map[i][j] == 'S') {
sY = i;
sX = j;
}
}
}
그럼 이제 지도에는 S, ., #, E, 0 ~ 4가 존재할 것이고, BFS를 시작점 S에서 부터 탐색을 한다.
1) '0', '1', '2', '3', '4' 일 때
현재 방문한 정점이 위의 값 중 하나라면, 물건이 있는 곳이다. 이때 내가 이미 해당 물건을 챙겼는지 여부를 비트마스킹으로 체크한다.
만약 이미 챙겼던 물건이라면 item은 변화를 주지 않고 그저 방문한다.
아직 챙기지 않은 물건이라면 챙기고 방문한다.
if(map[ny][nx] >= '0' && map[ny][nx] <= '5'){
int num = map[ny][nx] - '0';
if( (item & (1 << num)) == 0){
nItem = item | (1 << num);
visit[ny][nx][nItem] = true;
Q.add(new Point(ny, nx, move + 1, nItem));
continue;
}
}
2) '#'와 숫자를 제외한 나머지
이때는 그냥 방문하기만 하면 된다.
# 종료 시퀀스
- 물건을 모두 챙겼는지? 현재 정점이 'E' 인지
# Code </>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Point{
int y, x, move, item;
public Point(int yy, int xx, int m, int it){
y=yy;
x=xx;
move=m;
item=it;
}
}
//n : 높이, m : 너비, k : 물건의 개수
static int n, m, k;
static int[] Y = {-1,1,0,0}, X={0,0,-1,1};
static char[][] map = new char[51][51];
static boolean[][][] visit = new boolean[51][51][(1 << 6)];
static int BFS(int sy, int sx) {
Queue<Point> Q = new LinkedList<>();
visit[sy][sx][0] = true;
Q.add(new Point(sy, sx, 0, 0));
while(!Q.isEmpty()){
Point p = Q.poll();
int y = p.y;
int x = p.x;
int move = p.move;
int item = p.item;
if(map[y][x] == 'E' && item == ((1 << k) - 1))
return move;
for(int a=0; a<4; a++){
int ny = y+Y[a];
int nx = x+X[a];
int nItem = 0;
if(ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx][item] || map[ny][nx] == '#') continue;
if(map[ny][nx] >= '0' && map[ny][nx] <= '5'){
int num = map[ny][nx] - '0';
if( (item & (1 << num)) == 0){
nItem = item | (1 << num);
visit[ny][nx][nItem] = true;
Q.add(new Point(ny, nx, move + 1, nItem));
continue;
}
}
visit[ny][nx][item] = true;
Q.add(new Point(ny, nx, move + 1, item));
}
}
return 0;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
int sY = 0, sX = 0;
char idx = '0';
for(int i=1; i<=n; i++) {
char[] str = br.readLine().toCharArray();
for (int j = 1; j <= m; j++) {
map[i][j] = str[j - 1];
if (map[i][j] == 'X') {
map[i][j] = idx++;
k++;
} else if (map[i][j] == 'S') {
sY = i;
sX = j;
}
}
}
System.out.println(BFS(sY, sX));
}
}
반응형
'Programming > 백준' 카테고리의 다른 글
[백준] 9655번 : 돌 게임 (0) | 2021.05.10 |
---|---|
[백준] 16768번 : Mooyo Mooyo (0) | 2021.05.08 |
[백준] 12886번 : 돌 그룹 (0) | 2021.05.02 |
[백준] 14950번 : 정복자 (0) | 2021.05.02 |
[백준] 2562번 : 최댓값 (0) | 2021.05.01 |
Comments