성능 요약
메모리: 19164 KB, 시간: 220 ms
분류
너비 우선 탐색, 비트마스킹, 브루트포스 알고리즘, 그래프 이론, 그래프 탐색
제출 일자
2025년 3월 4일 01:52:37
문제 설명
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
.: 깨끗한 칸*: 더러운 칸x: 가구o: 로봇 청소기의 시작 위치
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
풀이
느낀점
- bfs로 그냥 풀릴것 같은데 왜 골드 1인가 했더니, 예외가 많은 문제였다.
- 질문게시판을 보고 나서야 풀이를 바꿔서 해결할 수 있었다..
- 풀이법을 바꾸고 나서는 간단하게 풀렸다. 함정이 있는 문제다.
설계 : 20분
- bfs로 모든 더러운 칸 사이의 최단거리를 저장한 후, dfs로 모든 칸을 방문하는 순서를 탐색하며 최단 거리를 구한다.
- 더러운 칸마다 인덱스를 부여하여 방문처리와 dfs에 용이하도록 했다.
코드(Java)
- 구현 시간: 100분
/**
* Author: yngbao97, Yuk Yejin
* Problem: 로봇 청소기_4991
* Date: 2025.03.04
*/
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static int h;
static int w;
static int[][] room;
static int[][] dist;
static int answer;
static List<int[]> dirt;
static boolean[] used;
static int count;
static int[] dr = {-1, 0, 1, 0};
static int[] dc = {0, 1, 0, -1};
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] input = br.readLine().split(" ");
h = Integer.parseInt(input[1]);
w = Integer.parseInt(input[0]);
// 입력된 값에 따라 테케 진행 여부 판단
while (h != 0 && w != 0) {
// 사방탐색을 위한 패딩처리
room = new int[h+2][w+2];
Arrays.fill(room[0], -1);
Arrays.fill(room[h+1], -1);
// 방 상태 및 더러운 칸(청소기 초기위치 포함) 목록 입력
dirt = new ArrayList<>();
dirt.add(new int[] {0, 0}); // 청소기 초기위치는 인덱스 0에 저장할 것, 미리 채워두기
for (int i = 1; i <= h; i++) {
room[i][0] = room[i][w+1] = -1;
char[] tmp = br.readLine().toCharArray();
for (int j = 1; j <= w; j++) {
char c = tmp[j-1];
if (c == 'o') { // 시작점 저장 (방 상태에는 빈곳으로 0)
room[i][j] = 0;
dirt.set(0, new int[] {i, j});
} else if (c == '*') { // 더러운 칸 저장 (방 상태에는 dirt 인덱스로 저장)
room[i][j] = dirt.size();
dirt.add(new int[] {i, j});
} else if (c == 'x') room[i][j] = -1; // 벽은 -1로, 패딩과 동일하게
}
}
count = dirt.size(); // 더러운 칸의 개수(청소기 위치 포함)
dist = new int[count][count]; // dirt의 인덱스를 사용해서 모든 칸 사이의 최단거리 저장
for (int[] start : dirt) { // 모든 칸에서 시작하여 탐색
bfs(start);
}
answer = Integer.MAX_VALUE;
used = new boolean[count];
dfs(0, 1, 0); // 청소기 출발지부터 시작하여 모든 더러운 칸을 방문하는 순서 탐색
if (answer == Integer.MAX_VALUE) bw.write("-1\n");
else bw.write(String.valueOf(answer) + "\n");
input = br.readLine().split(" ");
h = Integer.parseInt(input[1]);
w = Integer.parseInt(input[0]);
}
bw.flush();
bw.close();
br.close();
}
public static void dfs(int currIdx, int cnt, int sum) {
if(sum >= answer) return;
if(cnt >= count) {
answer = sum;
return;
}
// 청소기 시작 위치는 다시 갈 필요 없으므로, 1부터 순회
for (int i = 1; i < count; i++) {
if (used[i] || dist[currIdx][i] == 0) continue;
used[i] = true;
dfs(i, cnt + 1, sum + dist[currIdx][i]);
used[i] = false;
}
}
public static void bfs (int[] start) {
boolean[][] visited = new boolean[h+2][w+2];
Queue<int[]> queue = new ArrayDeque<>();
queue.add(start);
visited[start[0]][start[1]] = true;
int depth = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
if (room[curr[0]][curr[1]] > 0) dist[room[start[0]][start[1]]][room[curr[0]][curr[1]]] = depth;
for (int d = 0; d < 4; d++) {
int nr = curr[0] + dr[d];
int nc = curr[1] + dc[d];
if (room[nr][nc] < 0 || visited[nr][nc]) continue;
visited[nr][nc] = true;
queue.add(new int[] {nr, nc});
}
}
depth++;
}
}
}