[백준] code.plus(BFS 알고리즘,JAVA)4991번, 로봇 청소기

문제 링크

4991번: 로봇 청소기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 출발 지점에서 모든 먼지를 청소할 때 최소 이동횟수를 구해서 결과로 출력한다.

2. 'o'는 출발 지점, '.'은 깨끗한 공간, '*' 먼지가 존재하는 공간, 'x' 막힌 공간

3. 청소기는 상하좌우로 이동하며 막힌 공간으로는 이동하지 못한다.

4. 로봇은 같은 칸을 여러번 반복해도 된다.

 

알고리즘 진행 순서.

 

1. 초기 방에 시작지점과 먼지들에게 번호를 부여합니다.

 

2. 시작지점과 각 먼지들 사이의 최소 거리를 BFS 탐색으로 구합니다.

 

3. 브루트포스로 시작지점에서 먼지를 지나는 경로를 만들어 이동하는 최소값을 구해서 결과로 출력합니다.

 

예제입력 1.

 

TC1.

 

.	.	.	.	.	.	.
.	o(시작지점)	.	.	.	*	.
.	.	.	.	.	.	.
.	*	.	.	.	*	.
.	.	.	.	.	.	.

1. 초기 방에 시작지점과 먼지들에게 번호를 부여합니다.

 

.	.	.	.	.	.	.
.	1(시작지점)	.	.	.	2	.
.	.	.	.	.	.	.
.	3	.	.	.	4	.
.	.	.	.	.	.	.

 

2. 시작지점과 각 먼지들 사이의 최소 거리를 BFS 탐색으로 구합니다.

 

먼지 번호	1	2	3	4
1	0	4	2	6
2	4	0	6	2
3	2	6	0	4
4	6	2	4	0

3. 브루트포스로 시작지점에서 먼지를 지나는 경로를 만들어 이동하는 최소값을 구해서 결과로 출력합니다.

 

항상 시작 지점부터 로봇 청소기는 출발한다.

1 -> 2 -> 3 -> 4 = 4 + 6 + 4 = 14

1 -> 2 -> 4 -> 3 = 4 + 2 + 4 = 10

1 -> 3 -> 2 -> 4 = 2 + 6 + 2 = 10

1 -> 3 -> 4 -> 2 = 2 + 4 + 2 = 8

1 -> 4 -> 2 -> 3 = 6 + 2 + 6 = 14

1 -> 4 -> 3 -> 2 = 6 + 4 + 6 = 16

 

최소 이동값 8를 결과로 출력한다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 방에 대한 정보를 저장하였습니다.
• 각 먼지들 사이의 거리를 BFS탐색으로 구하는 dustRoute함수를 실행하였습니다.
• 모든 먼지를 청소할 수 있는지 확인하는 dustCheck함수를 실행하였습니다.
• 모든 먼지를 청소하지 못하면 -1, 청소하면 cal함수를 실행하여 최소 이동거리를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal는 시작지점에서 각 먼지들의 모든 경로에서 최소 이동횟수를 구하는 함수입니다.
• dustCheck은 모든 먼지를 청소할 수 있는지 확인하는 함수입니다.
• dustRoute은 입력된 먼지에서 다른 먼지까지의 BFS탐색으로 거리를 구하는 함수입니다.
• inRoom은 이동한 좌표가 방에 존재하는지 확인하는 함수입니다.

 

import java.util.*;
import java.io.*;

public class Main {
    //방에서 로봇 이동에 대한 클래스
    static class position{
        int x, y, count;
        public position(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
    static char[][] room;	//방에 대한 정보 저장 배열
    static int startX,startY;	//로봇 청소기 시작 x,y 값
    static int[][] dust, dustWidth;		//먼지 번호 및 먼지끼리 최단 경로 저장 배열
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x 변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y 변경값
    static boolean[] dustVisited;		//먼지 방문 확인 함수
    static int answer, dustIndex;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st;
        //TC 진행!
        while(true){
            st = new StringTokenizer(br.readLine()," ");
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            if(w == 0 && h == 0)	//TC 종료
                break;
            dustIndex = 2;
            room = new char[h][w];
            dust = new int[h][w];
            //입력값 저장 및 먼지 번호 매기기
            for(int i=0;i<h;i++){
                String str = br.readLine();
                for(int j=0;j<w;j++) {
                    room[i][j] = str.charAt(j);
                    if(room[i][j] == 'o'){
                        startX = j;
                        startY = i;
                        dust[i][j] = 1;	//시작 지점은 항상 번호 1
                    }else if(room[i][j] == '*')	//먼지 번호 매기기
                        dust[i][j] = dustIndex++;
                }
            }
            dustWidth = new int[dustIndex][dustIndex];
            dustVisited = new boolean[dustIndex];
            //먼지끼리의 최단 경로 구하기
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    if(dust[i][j] != 0){
                        dustRoute(h, w, j, i, dust[i][j]);	//최단 경로 구하는 BFS함수 실행
                    }
                }
            }
            if(dustCheck()){		//모든 먼지를 도달할 경우
                answer = Integer.MAX_VALUE;
                cal(1, 1, 0);	//모든 경로를 탐색하여 최소값 구하는 함수 실행
                bw.write(answer + "\n");
            }else		//모든 먼지를 도달하지 못한 경우
                bw.write("-1\n");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //모든 먼지를 청소하는지 확인하는 함수
    static boolean dustCheck(){
        for(int i=2;i<dustIndex;i++){
            if(dustWidth[1][i]==0)
                return false;
        }
        return true;
    }
    //모든 경로를 구해서 최소값을 구하는 재귀 함수
    static void cal(int cur, int count, int value){
        if(count==dustIndex-1)
            answer = Math.min(answer,value);

        for(int i=2;i<dustIndex;i++){
            if(dustVisited[i])
                continue;
            dustVisited[i] = true;
            cal(i, count+1, value + dustWidth[cur][i]);
            dustVisited[i] = false;
        }
    }
    //입력된 먼지 사이에 거리를 구하는 BFS 탐색하는 함수
    static void dustRoute(int h, int w, int x, int y, int index){
        Queue<position> queue = new LinkedList<>();
        boolean[][] visited = new boolean[h][w];
        visited[y][x] = true;
        queue.add(new position(x,y,0));
        while(!queue.isEmpty()){
            position cur = queue.poll();
            for(int i=0;i<4;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                if(inRoom(tempX,tempY,h,w) && !visited[tempY][tempX]){
                    visited[tempY][tempX] = true;
                    if(room[tempY][tempX] != 'x'){	//벽에 막히지 않는 경우
                        if(dust[tempY][tempX]!=0)	//다른 먼지 도달 시
                            dustWidth[index][dust[tempY][tempX]] = cur.count+1;
                        queue.add(new position(tempX,tempY, cur.count+1));
                    }
                }
            }
        }
    }
    //좌표가 방 안에 존재하는지 확인하는 함수
    static boolean inRoom(int x, int y, int h, int w){
        if(x>=0 && y>=0 && x<w && y<h)
            return true;
        return false;
    }
}