[Gold II] 아맞다우산 - 17244
성능 요약
메모리: 99772 KB, 시간: 360 ms
분류
너비 우선 탐색(bfs), 비트마스킹(bitmask), 브루트포스 알고리즘(bruteforcing), 그래프 이론(graphs), 그래프 탐색(graph_traversal)
문제 설명
경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다.
"아 맞다 우산!!!"
경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다.
외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다.
평소 불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빠르게 챙겨서 외출하는 이동 경로를 알고 싶었다.
경재 씨는 한 걸음에 상하좌우에 인접한 칸으로만 움직일 수 있다.
경재 씨를 위해 집을 위에서 바라본 모습과 챙겨야 할 물건들의 위치들을 알고 있을 때, 물건을 모두 챙겨서 외출하기까지 최소 몇 걸음이 필요한지 구하는 프로그램을 작성하자.
입력
첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50)
두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다.
비어있는 곳은 '.'로 벽은 '#'로 입력된다. 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다.
챙겨야 하는 물건은 최대 5개까지 있을 수 있다. 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다.
출력
S에서 출발하여 모든 물건을 챙겨서 E까지 도착할 수 있는 최소 시간을 출력한다. 모든 물건을 챙길 수 없는 경우는 주어지지 않는다.
풀이
챙겨야 하는 물건이 최대 5개이기 때문에 가능한 순서의 조합을 순열로 만들었다.
static void perm(int depth) {
if (depth == itemCnt) {
bfs();
return;
}
for (int i = 0; i < itemCnt; i++) {
if (!pick[i]) {
pick[i] = true;
order[depth] = i;
perm(depth + 1);
pick[i] = false;
}
}
}
처음에는 비트마스킹을 활용해서 방문 여부를 조회하며 검사하려고 했는데 뭔가 꼬였는지 잘 안돼서 바꿨다..
모든 경우의 수에 bfs를 수행하고 E를 방문했을 때의 time을 ans에 업데이트해준다.
bfs는 방문할 순서를 정한 order배열을 돌며 챙겨야 할 item을 목적지로 설정하고, 목적지에 도착하면 queue를 모두 비우고 다시 다음 목적지로 bfs를 계속한다.
static void bfs() {
Queue<int[]> q = new LinkedList<>();
int R = start_r;
int C = start_c;
int Time = 0;
int[][] visit = new int[M][N];
for (int i = 0; i < M; i++)
Arrays.fill(visit[i], -1);
out: for (int i = 0; i < itemCnt; i++) {
Items item = items.get(order[i]); // 방문할 곳
int dest_r = item.r;
int dest_c = item.c;
int id = item.id;
q.add(new int[]{R, C, Time});
while (!q.isEmpty()) {
int[] tmp = q.poll();
int r = tmp[0];
int c = tmp[1];
int time = tmp[2];
if (r == dest_r && c == dest_c) {
// 목적지까지 도착함, 다음으로 이동
q.clear();
R = dest_r;
C = dest_c;
Time = time;
continue out;
}
if (visit[r][c] == id) continue;
visit[r][c]=id;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if ((map[nr][nc] == '.' || map[nr][nc]=='X')&& visit[nr][nc] != id) {
q.add(new int[]{nr, nc, time + 1});
}
}
}
}
q.add(new int[]{R, C, Time});
// 마지막에는 E를 향해서 ㄱㄱ
while (!q.isEmpty()) {
int[] tmp = q.poll();
int r = tmp[0];
int c = tmp[1];
int time = tmp[2];
if (map[r][c] == 'E') {
// 목적지까지 도착함, 다음으로 이동
ans = Math.min(ans, time);
break;
}
if (visit[r][c] == 6) continue;
visit[r][c]=6;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (map[nr][nc] != '#' && visit[nr][nc] != 6) {
q.add(new int[]{nr, nc, time + 1});
}
}
}
}
전체 코드
import java.util.*;
public class Main {
static class Items {
int id;
int r;
int c;
public Items(int id, int r, int c) {
this.id = id;
this.r = r;
this.c = c;
}
}
static List<Items> items;
static int N, M;
static char[][] map;
static int start_r;
static int start_c;
static int[] order;
static boolean[] pick;
static int itemCnt;
static int[] dr = {1, -1, 0, 0};
static int[] dc = {0, 0, 1, -1};
static int ans = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
map = new char[M][N];
int[][] visited = new int[M][N];
for (int i = 0; i < M; i++)
Arrays.fill(visited[i], -1);
items = new ArrayList<>();
for (int i = 0; i < M; i++) {
String input = sc.next();
map[i] = input.toCharArray();
for (int j = 0; j < N; j++) {
if (map[i][j] == 'S') {
start_r = i;
start_c = j;
} else if (map[i][j] == 'X') {
items.add(new Items(items.size(), i, j));
}
}
}
itemCnt = items.size();
order = new int[itemCnt];
pick = new boolean[itemCnt];
perm(0);
System.out.println(ans);
}
static void perm(int depth) {
if (depth == itemCnt) {
bfs();
return;
}
for (int i = 0; i < itemCnt; i++) {
if (!pick[i]) {
pick[i] = true;
order[depth] = i;
perm(depth + 1);
pick[i] = false;
}
}
}
static void bfs() {
Queue<int[]> q = new LinkedList<>();
int R = start_r;
int C = start_c;
int Time = 0;
int[][] visit = new int[M][N];
for (int i = 0; i < M; i++)
Arrays.fill(visit[i], -1);
out: for (int i = 0; i < itemCnt; i++) {
Items item = items.get(order[i]); // 방문할 곳
int dest_r = item.r;
int dest_c = item.c;
int id = item.id;
q.add(new int[]{R, C, Time});
while (!q.isEmpty()) {
int[] tmp = q.poll();
int r = tmp[0];
int c = tmp[1];
int time = tmp[2];
if (r == dest_r && c == dest_c) {
// 목적지까지 도착함, 다음으로 이동
q.clear();
R = dest_r;
C = dest_c;
Time = time;
continue out;
}
if (visit[r][c] == id) continue;
visit[r][c]=id;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if ((map[nr][nc] == '.' || map[nr][nc]=='X')&& visit[nr][nc] != id) {
q.add(new int[]{nr, nc, time + 1});
}
}
}
}
q.add(new int[]{R, C, Time});
// 마지막에는 E를 향해서 ㄱㄱ
while (!q.isEmpty()) {
int[] tmp = q.poll();
int r = tmp[0];
int c = tmp[1];
int time = tmp[2];
if (map[r][c] == 'E') {
// 목적지까지 도착함, 다음으로 이동
ans = Math.min(ans, time);
break;
}
if (visit[r][c] == 6) continue;
visit[r][c]=6;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (map[nr][nc] != '#' && visit[nr][nc] != 6) {
q.add(new int[]{nr, nc, time + 1});
}
}
}
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 11066 - 파일 합치기 (자바 Java) (0) | 2022.10.23 |
---|---|
[백준] 7579 - 앱 (자바 Java) (0) | 2022.10.21 |
[백준] 9466 - 텀 프로젝트 (자바 Java) (0) | 2022.10.17 |
[백준] 17281 - ⚾ (자바 Java) (1) | 2022.10.13 |
[백준] 17136 - 색종이 붙이기 (자바 Java) (0) | 2022.10.13 |