내 풀이
오답 풀이
인접한 칸 중 더러운 칸을 우선순위(가중치)로 두고 이동하지 않아도 되므로
BFS로 가구가 없는 칸으로의 탐색을 계속 진행하면서 더러운 칸을 만나면 청소 후 남은 더러운 칸 수를 -1 해준 후,
남은 더러운 칸이 0이 되었을 때의 거리값을 반환해주면 모든 칸을 청소한 최단 거리가 구해질 것이라 예상헀다.
다음 코드 실행 시 답이 아래와 같이 나온다.
j, k : 1 1
청소된 더러운 칸 : 3 1
청소된 더러운 칸 : 1 5
청소된 더러운 칸 : 3 5
(1, 1) ->
(2, 1) ->
(3, 1) ->
(3, 2) ->
(3, 3) ->
(3, 4) ->
(3, 5) ->
End
정답 : 6
j, k : 1 3
청소된 더러운 칸 : 11 2
청소된 더러운 칸 : 1 12
청소된 더러운 칸 : 11 12
(1, 3) ->
(2, 3) ->
(3, 3) ->
(4, 3) ->
(5, 3) ->
(5, 4) ->
(5, 5) ->
(6, 5) ->
(7, 5) ->
(7, 6) ->
(7, 7) ->
(7, 8) ->
(8, 8) ->
(9, 8) ->
(10, 8) ->
(11, 8) ->
(11, 9) ->
(11, 10) ->
(11, 11) ->
(11, 12) ->
End
정답 : 19
j, k : 1 2
정답 : -1첫 번째 예제의 진행 과정을 보면 1,5 칸까지 가지 않고 3,5에서 조기종료 되어 원래 답보다 2가 작게 반환된다.
이를 통해 BFS에서 totalDirty를 이용한 종료조건에서 문제가 있는 것을 알 수 있었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static List<Integer> w, h, result;
static List<char[][]> map;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
w = new ArrayList<>();
h = new ArrayList<>();
map = new ArrayList<>();
result = new ArrayList<>();
while (true) {
StringTokenizer st = new StringTokenizer(br.readLine());
int tw = Integer.parseInt(st.nextToken());
int th = Integer.parseInt(st.nextToken());
if (tw == 0 && th == 0) break; // 입력 종료 조건
w.add(tw);
h.add(th);
char[][] currentMap = new char[th][tw];
for (int i = 0; i < th; i++) {
String tmp = br.readLine();
currentMap[i] = tmp.toCharArray(); // 문자열을 char 배열로 변환
}
map.add(currentMap);
}
for (int i = 0; i < map.size(); i++) {
for (int j = 0; j < h.get(i); j++) {
for (int k = 0; k < w.get(i); k++) {
if (map.get(i)[j][k] == 'o') {
System.out.println("j, k : " + j + " " + k);
if (bfs(j, k, i)) {
System.out.println(result.get(i));
} else {
System.out.println(-1);
}
}
}
}
}
}
static boolean bfs(int x, int y, int num) {
Queue<Node> queue = new LinkedList<>();
int nh = h.get(num);
int nw = w.get(num);
boolean[][] visited = new boolean[nh][nw];
visited[x][y] = true;
queue.offer(new Node(x, y, 0, null));
int totalDirty = 0;
for (int i = 0; i < nh; i++) { // 전체 칸 돌면서 남은 더러운 칸이 있는지 확인
for (int j = 0; j < nw; j++) {
if (map.get(num)[i][j] == '*')
totalDirty++;
}
}
while (!queue.isEmpty()) {
Node cur = queue.poll();
if (map.get(num)[cur.x][cur.y] == '*') { // 더러운 칸 도달 시
System.out.println("청소된 더러운 칸 : " + cur.x + " " + cur.y);
map.get(num)[cur.x][cur.y] = '.'; // 칸 청소
totalDirty--; // 남은 더러운 칸 수 감소
if (totalDirty == 0) {
printPath(cur); // 경로 출력
result.add(cur.dis); // 모든 더러운 칸을 청소했으면 결과 추가
return true;
}
}
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx >= 0 && ny >= 0 && nx < nh && ny < nw && !visited[nx][ny] && map.get(num)[nx][ny] != 'x') {
visited[nx][ny] = true;
queue.offer(new Node(nx, ny, cur.dis + 1, cur));
}
}
}
return false;
}
static class Node {
int x, y, dis;
Node parent;
Node(int x, int y, int dis, Node parent) {
this.x = x;
this.y = y;
this.dis = dis;
this.parent = parent;
}
}
private static void printPath(Node node) {
Stack<Node> path = new Stack<>();
while (node != null) {
path.push(node);
node = node.parent; // 부모 노드를 통해 역추적
}
// 경로 역순 출력
while (!path.isEmpty()) {
Node step = path.pop();
System.out.println("(" + step.x + ", " + step.y + ") -> ");
}
System.out.println("End");
}
}
정답 풀이
BFS를 사용해 종료 조건을 바꾸고 어떤 방법을 다 사용해도 내가 생각한 방법으로는 풀리지 않았다.
정답 풀이를 찾아보니 DFS와 BFS를 둘 다 사용하는 방법으로 다들 풀었다.
먼저 BFS로 맵의 모든 칸을 시작점으로, 시작점부터 갈 수 있는 모든 지점까지의 최단 거리를 저장하고,
DFS로 더러운 칸의 청소 순서(순열)를 구해 각 순서로 더러운 칸을 청소한다고 했을 때 최단거리의 총합을 구하여 답을 반환한다.
정리해보면
BFS - o부터 모든 곳까지의 최단거리 구해놓기
DFS - 더러운 칸을 모두 사용해 만든 순열마다 BFS에서 구해놓은 최단거리를 더했을 때 최소가 되는 순열 찾기
정답 코드
import java.io.*;
import java.util.*;
public class Main {
public static class Node {
int x;
int y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
public static int h, w, minDis;
public static ArrayList<Node> dirty;
public static int startX, startY;
public static char[][] map;
public static boolean[] visited;
public static int[][][][] dis; // x, y 지점에서 nx, ny 지점까지의 최단거리 저장
public static int[] dx = {-1, 1, 0, 0};
public static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true){
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
if(h == 0 && w == 0) break; // 입력 종료 조건
dis = new int[h][w][h][w];
map = new char[h][w];
dirty = new ArrayList<>();
for(int i = 0; i< h; i++){
map[i] = br.readLine().toCharArray(); // 문자열을 char 배열로 변환
for(int j = 0; j< w; j++){
if(map[i][j] == '*'){
dirty.add(new Node(i, j));
} else if(map[i][j] == 'o'){
startX = i;
startY = j;
}
}
}
visited = new boolean[dirty.size()];
minDis = Integer.MAX_VALUE;
for(int i = 0; i< h; i++){
for(int j = 0; j< w; j++){
bfs(i, j); // i, j 부터 모든 접근 가능 지점까지의 최단거리 저장
}
}
dfs(0, new int[dirty.size()]); // 더러운 칸으로 만들 수 있는 모든 순열을 조합해 최단거리 구하기
if(minDis == Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(minDis);
}
}
public static void bfs(int x, int y){
Queue<Node> q = new LinkedList<>();
q.add(new Node(x, y));
while (!q.isEmpty()){
Node node = q.poll();
for(int i=0;i<4;i++){
int nx = node.x + dx[i];
int ny = node.y + dy[i];
if(nx < 0 || ny < 0 | nx >= h || ny >= w) continue;
if(map[nx][ny] == 'x') continue;
if(dis[x][y][nx][ny] != 0) continue;
q.add(new Node(nx, ny));
dis[x][y][nx][ny] = dis[x][y][node.x][node.y]+1;
}
}
}
public static void dfs(int depth, int[] perm){
if(depth == dirty.size()){
int disDFS = 0;
int nextX = startX;
int nextY = startY;
for(int i=0;i<perm.length;i++){
Node d = dirty.get(perm[i]);
int distance = dis[nextX][nextY][d.x][d.y];
if(distance == 0) return;
disDFS += distance;
nextX = d.x;
nextY = d.y;
}
minDis = Math.min(minDis, disDFS);
return;
}
for(int i=0;i<dirty.size();i++){
if(visited[i]) continue;
visited[i] = true;
perm[depth] = i;
dfs(depth+1, perm);
visited[i] = false;
}
}
}
짱이 되고싶은 개발 기록