https://www.acmicpc.net/problem/4991
4991번: 로봇 청소기
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
www.acmicpc.net
코드설명
완전탐색(BruteForce) + 순열(Permutation) + BFS(너비우선탐색) + DP(Dynamic Programming) 을 활용하는 문제입니다.
처음에는 시뮬레이션 + 구현 + 순열 + BFS(너비우선탐색) 를 활용해서 진행했지만, DP를 사용하지 않아 시간초과가 났습니다.
시간초과의 원인으로 아예 못가는 경우를 먼저 검사한뒤 해당 검사를 통과했을 경우에만 함수가 실행되도록 수정했는데도 시간초과가 났습니다. 순열을 통해 진행하며 매번 각 로봇에서 먼지까지의 거리를 BFS로 매번 검사한다는것이 시간초과의 원인이었습니다.
각 먼지 간의 거리를 미리 BFS로 모두 구한 것을 DP로 저장시킵니다.
그렇게할경우, 0번 먼지와 1 2 3 번 먼지의 거리
1번 먼지와 0 1 3 먼지의 거리를 구할 수 있습니다.
표로 보면,
| 먼지번호/먼지번호 | 0 | 1 | 2 | 3 |
| 0 | 0 | 4 | 2 | 6 |
| 1 | 4 | 0 | 6 | 2 |
| 2 | 2 | 6 | 0 | 4 |
| 3 | 6 | 2 | 4 | 0 |
위와 같습니다.
그리고, 각 먼지를 어떤 순서대로 접근할 것인지 순열로 구할 수 있습니다.
0 1 2 3, 0 1 3 2, 0 2 1 3, 0 2 3 1, 0 3 1 2 , 0 3 2 1
이런식으로 구할 수 있습니다. 이떄 0 번은 로봇이기에 고정적인 순서입니다.
중복순열과는 다릅니다. 중복순열이라면 0 1 1 1 이렇게 될 수 있습니다.
위의 DP를 통해 시간초과를 해결할 수 있었습니다.
추가로 문제에서 중요한점은,
1. 이 문제를 완전탐색(Brute Force)로 접근하느냐에 대한 시각이 필요합니다.
처음에는 단순히 DP[지금까지 청소한 먼지 갯수][r][c] 로 처리를 하려고했지만, 이렇게 할경우 이후에 다른 경로로 청소할 수 있는 경우에 같은 개수의 먼지 갯수를 청소한 청소기는 다른 청소기에 영향을 받아 탐색하지 못하는경우가 있을 수 있습니다.
그렇기에 각 먼지에서 먼지까지의 거리를 따로따로 구하여 모든 경로와 비교하는 방식으로 진행해야합니다.
2. 청소기를 먼지처럼 생각해야할 필요도 있습니다.
청소기 객체(Robot Node)를 활용하여 현재 청소기의 위치를 저장하고,
먼지 객체(Dirt Node)를 활용하여 먼지들을 관리하는데,
이떄 첫 시작 청소기 위치는 항상 정해져있습니다. 그렇기에 단순히 먼지의 맨 첫번쨰 위치에 로봇을 삽입함으로써 탐색하는 순서를 정할떄 훨씬 단순하게 구할 수 있습니다.
dirtArrList.add(0, new Dirt(row, col));
3. 로봇을 전역변수로 두고, 처리하는 방법과 Simulate(level, beforeRobotIdx)로 처리하는 방법 둘중 한개를 선택하라.
저는 1번 방법인 로봇을 전역변수로 두고 처리했습니다.
이렇게 한 이유는, 로봇을 전역적으로 관리하는 것이 조금 더 익숙해서 이런 방식으로 처리했습니다.
4. 최대값은 Integer.MAX_VALUE로 해도되지만, 20*20 칸에서 10개의 먼지를 청소하는 경우의 최대값은 아래와 같습니다.
public static int MAXVALUE = 21*21*10;
4. 전역변수와 지역변수에 대한 실수가 있었습니다.
아래의 코드를 전역으로 선언한뒤,
public static ArrayList<Dirt> dirtArrList;
다시 Main함수에 같은이름으로 재선언하여 Simulate함수에서 올바르게 전역변수를 처리하지 못하였습니다.
지역변수에 틀린 코드 : ArrayList<Dirt> dirtArrList = new ArrayList<>();
맞는 코드 : dirtArrList = new ArrayList<>();
코드
로봇청소기 또한 일종의 먼지로 판단하여 각 먼지 간의 먼지간의 거리를 2차원 배열로 DP 로 활용하여 연산시간을 줄입니다. 순열 DP BFS 를 활용합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K;
public static int answer = 0;
public static int[] arr;
public static char[][] map;
public static int[] dx = {-1,1,0,0};
public static int[] dy = {0,0,-1,1};
public static boolean[] permutationVisited;
public static int[][] distanceBetweenDustAndDust;
public static int dirtyPlace = 0;
public static Robot robot;
public static int h = 0, w = 0;
public static ArrayList<Dirt> dirtArraylist = new ArrayList<Dirt>();
public static int MAXVALUE = 20 * 20 + 1;
public static int robotIdx = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// StringTokenizer st = new StringTokenizer(br.readLine());
while(true) {
answer = MAXVALUE;
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken()); //열
h = Integer.parseInt(st.nextToken()); //행
if(w == 0 && h == 0) break;
map = new char[h][w];
for(int i=0;i<h;i++) {
st = new StringTokenizer(br.readLine());
map[i] = st.nextToken().toCharArray();
}
dirtyPlace = 0;
dirtArraylist.clear();
for(int i=0;i<h;i++) {
for(int j=0;j<w;j++) {
if(map[i][j] == '*') { //만약 더러운 공간이라면 개수를 미리 세둡니다.
dirtyPlace += 1;
dirtArraylist.add(new Dirt(i, j));
}
else if(map[i][j] == 'o') {
robot = new Robot(i, j, 0);
dirtyPlace += 1;
dirtArraylist.add(0, new Dirt(i,j));
}
}
}
distanceBetweenDustAndDust = new int[dirtyPlace][dirtyPlace];
boolean flag = true;
for(int i=0;i<dirtyPlace;i++) {
for(int j=i+1;j<dirtyPlace;j++) {
int distance = DistanceBetweenDirtAndDirtBFS(dirtArraylist.get(i), dirtArraylist.get(j));
distanceBetweenDustAndDust[i][j] = distanceBetweenDustAndDust[j][i] = distance;
if(i == 0 && distance >= MAXVALUE) { //만약 청소기의 위치에서 못가는 먼지가 존재한다면, 실패합니다.
flag = false;
break;
}
}
if(flag == false) break;
}
if(flag == false) {
System.out.println("-1");
continue;
}
//먼저 전체적으로 갈 수 있는지 한번 체크하고 들어갑니다. 만약 1개라도 실패한다면 중단시킵니다.
permutationVisited = new boolean[dirtyPlace];
answer = MAXVALUE;
//순열을 기반으로 하여 완전탐색을 수행합니다.
simulate(0, 0);
if(answer >= MAXVALUE) {
System.out.println(-1);
}else {
System.out.println(answer);
}
}
}
public static int DistanceBetweenDirtAndDirtBFS(Dirt a, Dirt b) {
Queue<Dirt> q = new LinkedList<Dirt>();
q.offer(a);
int[][] lengthVisited = new int[h][w];
for(int i=0;i<h;i++) {
Arrays.fill(lengthVisited[i], MAXVALUE);
}
lengthVisited[a.r][a.c]= 0;
while(!q.isEmpty()) {
Dirt temp = q.poll();
if(temp.r == b.r && temp.c == b.c) {
return lengthVisited[temp.r][temp.c];
}
for(int dir = 0; dir < 4 ; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
if(lengthVisited[nr][nc] != MAXVALUE) continue;
if(map[nr][nc] == 'x') continue;
lengthVisited[nr][nc] = lengthVisited[temp.r][temp.c] + 1;
q.offer(new Dirt(nr, nc));
}
}
return MAXVALUE;
}
public static void simulate(int level, int idx) {
if(level == dirtyPlace - 1) {
answer = Math.min(answer, robot.cnt);
return ;
}
for(int i=1;i<dirtyPlace;i++) {
if(permutationVisited[i] == false) {
//로봇을 이동시킵니다.
int distance = distanceBetweenDustAndDust[robotIdx][i];
if(distance >= MAXVALUE) continue;
int beforeRobotIdx = robotIdx;
int beforeRobotCnt = robot.cnt;
robotIdx = i;
robot.cnt += distance;
permutationVisited[i] = true;
simulate(level + 1, i + 1);
permutationVisited[i] = false;
//원상복구 시킵니다.
robotIdx = beforeRobotIdx;
robot.cnt = beforeRobotCnt;
}
}
}
}
class Dirt{
int r;
int c;
public Dirt(int r, int c) {
this.r=r;
this.c=c;
}
}
class Robot{
int r;
int c;
int cnt;
public Robot(int r, int c, int cnt) {
this.r = r;
this.c = c;
this.cnt = cnt;
}
}
통과하는 코드.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int w, h;
public static int MAXVALUE = 21*21*10;
public static int answer = MAXVALUE;
public static char[][] map;
public static ArrayList<Dirt> dirtArrList;
public static boolean[] permVisited;
public static int[][] distanceDP;
public static Robot robot;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// StringTokenizer st = new StringTokenizer(br.readLine());
while(true) {
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken()); //가로 (COL)
h = Integer.parseInt(st.nextToken()); //세로 (ROW)
if(w == 0 && h == 0) return ;
map = new char[h][w];
for(int row=0;row<h;row++) {
st = new StringTokenizer(br.readLine());
map[row] = st.nextToken().toCharArray();
}
dirtArrList = new ArrayList<Dirt>();
for(int row=0;row<h;row++) {
for(int col=0;col<w;col++) {
if(map[row][col] == '*') {
dirtArrList.add(new Dirt(row, col));
}
else if(map[row][col] == 'o') { //로봇 청소기의 시작위치는 항상 0 번째 인덱스로 선언한다.
dirtArrList.add(0, new Dirt(row, col));
robot = new Robot(row, col, 0, 0);
}
}
}
permVisited = new boolean[dirtArrList.size()];
answer = MAXVALUE;
distanceDP = new int[dirtArrList.size()][dirtArrList.size()];
for(int i=0;i<dirtArrList.size(); i++) {
Arrays.fill(distanceDP[i], MAXVALUE);
}
//먼저 distanceDP[dirtArrList.size()][dirtArrList.size()] 에 대한 DP배열을 먼저 만들어놓을 것 입니다.
for(int i=0;i<dirtArrList.size();i++) {
for(int j=i;j<dirtArrList.size();j++) {
if(i == j) {
distanceDP[i][j] = distanceDP[j][i] = 0;
}
else {
distanceDP[i][j] = distanceDP[j][i] = getDistanceByBFS(dirtArrList.get(i), dirtArrList.get(j));
}
}
}
//로봇청소기인 dirtArrList.get(0) 번을 이미 선택하므로 Level : 1 로 시작하며, beforeRobotIdx는 이전 로봇의 위치를 저장하며 이동합니다.
simulate(1);
if(answer == MAXVALUE) {
System.out.println("-1");
}else
System.out.println(answer);
}
}
public static int getDistanceByBFS(Dirt start, Dirt target) {
int[] dx = {-1,1,0,0};
int[] dy = {0,0,-1,1};
boolean[][] visited = new boolean[h][w];
Queue<Dirt> q = new LinkedList<>();
q.offer(new Dirt(start.r, start.c, 0));
visited[start.r][start.c] = true;
while(!q.isEmpty()) {
Dirt temp = q.poll();
if(temp.r == target.r && temp.c == target.c) {
return temp.cnt;
}
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
if(visited[nr][nc] == true) continue;
if(map[nr][nc] =='x') continue;
visited[nr][nc] = true;
q.offer(new Dirt(nr, nc, temp.cnt + 1));
}
}
return MAXVALUE;
}
public static void simulate(int level) {
if(level == dirtArrList.size()) {
answer = Math.min(answer, robot.moved);
return ;
}
Robot storeRobot = new Robot(robot.r, robot.c, robot.moved, robot.robotIdx);
for(int i=1; i<dirtArrList.size();i++) {
if(permVisited[i] == false) {
//beforeRobotIdx와 dirtArrList의 먼지와의 거리 구한뒤 이동.
int distance = distanceDP[robot.robotIdx][i];
permVisited[i] = true;
robot.robotIdx = i;
robot.r = dirtArrList.get(i).r; robot.c = dirtArrList.get(i).c; robot.moved += distance;
simulate(level + 1);
//로봇 제자리 시킵니다.
permVisited[i] = false;
robot.robotIdx = storeRobot.robotIdx;
robot.r = storeRobot.r; robot.c = storeRobot.c; robot.moved = storeRobot.moved;
}
}
}
}
class Dirt{
int r;
int c;
int cnt = 0;
public Dirt(int r, int c) {
this.r=r;
this.c=c;
}
public Dirt(int r, int c, int cnt) {
this.r=r;
this.c=c;
this.cnt = cnt;
}
}
class Robot{
int r;
int c;
int moved;
int robotIdx;
public Robot(int r, int c) {
this.r=r;
this.c=c;
}
public Robot(int r, int c, int moved) {
this.r=r;
this.c=c;
this.moved=moved;
}
public Robot(int r, int c, int moved, int robotIdx) {
this.r=r;
this.c=c;
this.moved=moved;
this.robotIdx = robotIdx;
}
}
BFS와 순열을 함께 사용하여 시간초과가 나는 코드입니다.
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 {
public static int N, M, K;
public static int answer = 0;
public static int[] arr;
public static char[][] map;
public static int[] dx = {-1,1,0,0};
public static int[] dy = {0,0,-1,1};
public static boolean[][] visited;
public static boolean[] permutationVisited;
public static int dirtyPlace = 0;
public static Robot robot;
public static int h = 0, w = 0;
public static ArrayList<Dirt> dirtArraylist = new ArrayList<Dirt>();
public static int MAXVALUE = 20 * 20 + 1;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// StringTokenizer st = new StringTokenizer(br.readLine());
while(true) {
answer = MAXVALUE;
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken()); //열
h = Integer.parseInt(st.nextToken()); //행
if(w == 0 && h == 0) break;
map = new char[h][w];
for(int i=0;i<h;i++) {
st = new StringTokenizer(br.readLine());
map[i] = st.nextToken().toCharArray();
}
dirtyPlace = 0;
dirtArraylist.clear();
for(int i=0;i<h;i++) {
for(int j=0;j<w;j++) {
if(map[i][j] == '*') { //만약 더러운 공간이라면 개수를 미리 세둡니다.
dirtyPlace += 1;
dirtArraylist.add(new Dirt(i, j));
}
else if(map[i][j] == 'o') {
robot = new Robot(i, j, 0);
}
}
}
if( canRobotReachEveryDirt() == false ) {
System.out.println("-1");
continue;
}
//먼저 전체적으로 갈 수 있는지 한번 체크하고 들어갑니다. 만약 1개라도 실패한다면 중단시킵니다.
permutationVisited = new boolean[dirtyPlace];
answer = MAXVALUE;
//순열을 기반으로 하여 완전탐색을 수행합니다.
simulate(0, 0);
if(answer >= MAXVALUE) {
System.out.println(-1);
}else {
System.out.println(answer);
}
}
}
public static boolean canRobotReachEveryDirt() {
int dirtCount = 0;
Queue<Robot> q = new LinkedList<>();
q.offer(new Robot(robot.r, robot.c, 0));
visited = new boolean[h][w];
visited[robot.r][robot.c]= true;
while(!q.isEmpty()) {
Robot temp = q.poll();
if(map[temp.r][temp.c] =='*') {
dirtCount += 1;
}
for(int dir = 0; dir< 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
if(visited[nr][nc] == true) continue;
if(map[nr][nc] == 'x') continue;
visited[nr][nc] = true;
q.offer(new Robot(nr, nc, temp.cnt + 1));
}
}
if(dirtCount == dirtyPlace) {
return true;
}
return false;
}
public static void simulate(int level, int idx) {
if(level == dirtyPlace) {
answer = Math.min(answer, robot.cnt);
return ;
}
for(int i=0;i<dirtyPlace;i++) {
if(permutationVisited[i] == false) {
//로봇을 이동시킵니다.
int distance = RobotToDirtBfs(dirtArraylist.get(i));
if(distance >= MAXVALUE) continue;
Robot beforeRobot = new Robot(robot.r, robot.c, robot.cnt);
map[dirtArraylist.get(i).r][dirtArraylist.get(i).c] = '.';
robot.r = dirtArraylist.get(i).r; robot.c = dirtArraylist.get(i).c; robot.cnt += distance;
permutationVisited[i] = true;
simulate(level + 1, i + 1);
permutationVisited[i] = false;
//원상복구 시킵니다.
robot.r = beforeRobot.r; robot.c = beforeRobot.c; robot.cnt = beforeRobot.cnt;
map[dirtArraylist.get(i).r][dirtArraylist.get(i).c] = '*';
}
}
}
public static int RobotToDirtBfs(Dirt curDirt) {
Queue<Robot> q = new LinkedList<Robot>();
q.offer(new Robot(robot.r, robot.c, 0)); //이 부분에서 카운트값을 올바르게 세기 위해서는 cnt를 0 으로 처리해야합니다.. 처음에 전역변수값 robot.cnt를 넣거나ㅣ q.offer(robot)으로 햇다가 게속 오류가 났었습니다. BFS를 통해 한점에서 한점까지의 거리를 구한다는 것을 기억해야합니다.
visited = new boolean[h][w];
visited[robot.r][robot.c]= true;
while(!q.isEmpty()) {
Robot temp = q.poll();
if(curDirt.r == temp.r && curDirt.c == temp.c) {
return temp.cnt;
}
for(int dir = 0; dir<4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
if(visited[nr][nc] == true) continue;
if(map[nr][nc] =='x') continue;
visited[nr][nc] = true;
q.offer(new Robot(nr, nc, temp.cnt + 1));
}
}
return MAXVALUE;
}
}
class Dirt{
int r;
int c;
public Dirt(int r, int c) {
this.r=r;
this.c=c;
}
}
class Robot{
int r;
int c;
int cnt;
public Robot(int r, int c, int cnt) {
this.r = r;
this.c = c;
this.cnt = cnt;
}
}
처음에는 단순히 청소기 시점에서 Visisted[청소한 먼지][Row][Col]로써 방문처리하며 BFS를 돌면 각 청소기 Node가 최소 거리를 찾는경우 중단되며 해당 거리가 최소값일 것이라고 생각했습니다.
하지만 이렇게 할경우 만약 청소한 먼지의 개수가 겹칠때 서로 이동하지 못하는 경우가 발생합니다.
즉, 이미 2개의 먼지를 청소한경우와 다른 2개의 먼지를 청소한 경우에서 길이 겹치는 경우가 발생하여 독립적이지 않고 서로 영향을 주는 결과가 나옵니다.
그러므로, 각 이동방향을 먼저 정해두고 경로마다 따로 BFS를 돌려서 최단거리를 찾아가는 방법이 유효합니다.
package Main;
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 {
public static int w, h;
public static int answer = 0;
public static int dirtCnt = 0;
public static char[][] map;
public static Queue<Node> q = new LinkedList<>();
public static boolean[][][] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// StringTokenizer st = new StringTokenizer(br.readLine());
while(true) {
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken()); //w가 가로이다.(col)
h = Integer.parseInt(st.nextToken()); //h가 세로이다.(row)
if(w == 0 && h == 0) break;
map = new char[h][w];
visited = new boolean[11][h][w];
q.clear();
dirtCnt = 0;
answer = Integer.MAX_VALUE;
for(int row=0; row<h;row++) {
st = new StringTokenizer(br.readLine());
// for(int col=0; col<w;col++) {
map[row] = st.nextToken().toCharArray();
// }
for(int col=0; col<w;col++) {
if(map[row][col] == '*') dirtCnt += 1;
else if(map[row][col] == 'o') {
visited[0][row][col] = true;
q.offer(new Node(row, col, 0, 0));
}
}
}
// System.out.println(dirtCnt);
simulate();
if(answer == Integer.MAX_VALUE) {
System.out.println(-1);
}else {
System.out.println(answer);
}
}
}
public static void simulate() {
int[] dx = {-1,1,0,0};
int[] dy = {0,0,-1,1};
while(!q.isEmpty()) {
Node temp = q.poll();
if(temp.dirtCleanCnt == dirtCnt) {
answer = Math.min(answer, temp.time);
return ;
}
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
if(map[nr][nc] == 'x') continue;
if(visited[temp.dirtCleanCnt][nr][nc] == true) continue;
//만약 꺠끗한 칸 이라면,
if(map[nr][nc] == '.') {
visited[temp.dirtCleanCnt][nr][nc] = true;
q.offer(new Node(nr, nc, temp.dirtCleanCnt, temp.time + 1));
}
//만약 먼지를 만난다면,
else if(map[nr][nc] == '*') {
visited[temp.dirtCleanCnt + 1][nr][nc] = true;
q.offer(new Node(nr, nc, temp.dirtCleanCnt + 1, temp.time + 1));
}
}
}
}
}
class Node{
int r;
int c;
int dirtCleanCnt = 0;
int time;
public Node(int r, int c, int dirtCleanCnt, int time) {
this.r=r;
this.c=c;
this.dirtCleanCnt = dirtCleanCnt;
this.time = time;
}
}