문제풀이
'로봇 청소기로 가장 가까운 더러운 곳을 BFS로 찾고 그 지점에서 다시 가장 가까운 지점을 BFS로 찾는다.' 라는 아이디어로 즐겁게 구현했지만... 바로 틀렸습니다를 보게 되었다... 위 아이디어의 문제점을 살펴보자면
- 그리디한 방법이다. 현재 지점에서 가장 가까운 지점을 방문해나가지만 전체적으로 보았을 때 최소거리로 모든 지점을 방문한 것이 아니다.
그래서 모든 지점 사이에 거리를 구하고 그를 바탕으로 모든 지점을 방문했을 때 최소거리가 되는 경로를 찾기로 하였다.
- 각 지점사이의 거리를 나타내는
dis[][]배열을 만들고 각 지점 사이의 최소 거리를 BFS로 찾아서 기록하였다.
- 로봇청소기는 지나간 곳을 다시 지나갈 수 있다는 말 때문에 방문체크를 사용하지 말아야되나? 라는 생각을 했지만, 그것은 전체적으로 보았을 때고 두 지점 사이의 최소 거리를 구할 때는 방문체크를 하는 것이 훨씬 효율적이다.- 한 지점에서 다른 모든 지점으로의 최소 거리를 구하는데 닿지 못한다면
-1을 리턴한다.
- 한 지점에서 다른 모든 지점으로의 최소 거리를 구하는데 닿지 못한다면
- DFS로 순열을 구하듯이 모든 지점을 방문하는 모든 방법을 조합해보며 최소값을 갱신한다.
한참동안 계속 틀리다가 겨우 문제점을 찾았는데... 닿지 못하는 지점이 있을 때 -1을 리턴해버리는 바람에 프로그램이 종료되는 것이였다. 코드를 잘 읽자!!!
구현코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Node {
int r, c;
Node(int r, int c) {
this.r = r;
this.c = c;
}
}
static ArrayList<Node> list;
static int[][] dis;
static boolean[] selected;
static char[][] map;
static int R, C, ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
while (true) {
// 데이터 입력받기
st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
// 0, 0을 입력받는 경우 프로그램을 종료한다.
if (R == 0 && C == 0)
break;
map = new char[R][C];
list = new ArrayList<>();
// 더러운 곳 또는 로봇 청소기의 위치를 리스트에 저장한다.
for (int i = 0; i < R; ++i) {
char[] line = br.readLine().toCharArray();
for (int j = 0; j < C; ++j) {
map[i][j] = line[j];
if (map[i][j] == 'o') {
list.add(0, new Node(i, j));
} else if (map[i][j] == '*') {
list.add(new Node(i, j));
}
}
}
// 0번째는 로봇 청소기, 나머지는 더러운 곳
int size = list.size();
dis = new int[size][size];
selected = new boolean[size];
// 모든 지점 사이의 거리를 구한다. (로봇청소기, 더러운 곳)
for (int idx = 0; idx < size; ++idx) {
// 닿지 못하는 더러운 곳이 있다면 바로 종료
if (bfs(idx) == -1) {
ans = -1;
break;
}
}
if(ans == -1) {
System.out.println(ans);
continue; // 이번 테스트케이스를 종료하고 다음으로 넘어간다.
} else {
// 모든 경로중에 최소값을 찾는다.
ans = Integer.MAX_VALUE;
selected[0] = true;
dfs(0, 0, 0);
System.out.println(ans);
}
}
}
private static void dfs(int depth, int dist, int from) {
// 모든 지점을 방문했으면 최소값을 갱신하고 종료한다.
if (depth == selected.length - 1) {
ans = ans > dist ? dist : ans;
return;
}
for (int to = 1; to < selected.length; ++to) {
if (!selected[to]) {
selected[to] = true;
// 거리인접행렬에서 값을 꺼내 더하고 다음 지점으로 향한다.
dfs(depth + 1, dist + dis[from][to], to);
selected[to] = false;
}
}
}
private static int bfs(int from) {
// 로봇청소기가 지나갔던 길을 다시 갈 수 있지만
// 각 지점 사이의 최소거리는 방문체크를 했을 때 더 빠르게 찾는다.
boolean[][] visited = new boolean[R][C];
int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
Queue<Node> q = new LinkedList<>();
int dust = 0;
int cnt = 0;
Node start = list.get(from);
visited[start.r][start.c] = true;
q.offer(start);
while (!q.isEmpty()) {
int size = q.size();
cnt++;
for (int i = 0; i < size; ++i) {
Node cur = q.poll();
for (int d = 0; d < 4; ++d) {
int nr = cur.r + dir[d][0];
int nc = cur.c + dir[d][1];
if (nr >= R || nr < 0 || nc >= C || nc < 0 || visited[nr][nc] || map[nr][nc] == 'x')
continue;
if (map[nr][nc] == 'o' || map[nr][nc] == '*') {
// 현재 도착한 지점이 몇번 인덱스 지점인지 찾는다.
for (int to = 0; to < list.size(); ++to) {
Node end = list.get(to);
if (end.r == nr && end.c == nc) {
// 거리배열을 갱신한다.
dis[from][to] = cnt;
dis[to][from] = cnt;
dust++;
}
}
}
visited[nr][nc] = true;
q.offer(new Node(nr, nc));
}
}
}
// 방문한 더러운 곳이 전체 더러운 곳 보다 작으면 닿지못하는 지점이 있는 것이다.
if (dust != list.size() - 1)
return -1;
else
return 0;
}
}
그냥 개발자