[백준] code.plus(BFS 알고리즘,JAVA)6087번, 레이저 통신

문제 링크

6087번: 레이저 통신

---

주의사항

• 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. 레이저 경로에 거울을 설치하면 90도로 회전하여 방향을 바꿉니다.

2. 레이저가 벽(*)에 맞으면 없어집니다.

3. 거울을 최소로 설치하여 각 레이저 출발 지점끼리 연결되도록하는 거울의 개수를 출력합니다.

 

거울의 설치에 따른  BFS탐색을 반복하고 가장 먼저 레이저가 연결되었을 때에 거울의 개수를 결과로 출력합니다.

 

거울 설치에 따라 BFS 탐색을 진행하기 위해 PriorityQueue<>을 사용하는 다익스트라 알고리즘을 사용하였습니다.

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

예제입력 1.

.	.	.	.	.	.	.
.	.	.	.	.	.	C
.	.	.	.	.	.	*
*	*	*	*	*	.	*
.	.	.	.	*	.	.
.	.	.	.	*	.	.
.	C	.	.	*	.	.
.	.	.	.	.	.	.

(1, 6)에서 BFS 탐색 시작

.	.	.	.	.	.	.
-	-	-	-	-	-	C
.	.	.	.	.	.	*
*	*	*	*	*	.	*
.	.	.	.	*	.	.
.	.	.	.	*	.	.
.	C	.	.	*	.	.
.	.	.	.	.	.	.

BFS 탐색....

.	.	.	.	.	.	.
.	.	.	.	.	/	C
.	.	.	.	.	|	*
*	*	*	*	*	|	*
.	.	.	.	*	|	.
.	.	.	.	*	|	.
.	C	.	.	*	|	.
.	\	-	-	-	/	.

사용한 거울의 수 : 3개

결과로 3 출력

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 지도에 대한 값들을 저장하였습니다.
• 'C'에 위치에 따라 다익스트라로 BFS탐색을 진행하여 레이저 연결되는 거울의 최소 개수를 구하는 bfs함수를 실행하였습니다.
• 사용된 거울의 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 PriorityQueue를 사용하여 사용된 개수를 이용하여 다익스트라 알고리즘을 수행하였습니다.
• bfs함수는 visited[][] 배열에는 해당 구역에 사용된 최소 거울 개수를 저장하였습니다.
• bfs함수는 레이저의 방향이 90도로 바뀔 때 거울의 개수가 추가됩니다.

 

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

public class Main {
    //레이저 연결할 좌표 관련 클래스
    static class position{
        int x, y;
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    //BFS탐색에 PriorityQueue에 사용할 레이저 관련 클래스
    static class laser implements Comparable<laser>{
        int x, y, mirror, direction;
        public laser(int x, int y, int mirror, int direction) {
            this.x = x;
            this.y = y;
            this.direction = direction;
            this.mirror = mirror;
        }
        @Override
        public int compareTo( laser o) {
            return this.mirror - o.mirror;
        }
    }
    static int W,H;
    static char[][] map;		//지도 관련 저장 배열
    static ArrayList<position> C = new ArrayList<>();	//레이저 연결 위치 저장 리스트
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x값 변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y값 변경값
    static public 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 = new StringTokenizer(br.readLine()," ");
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new char[H][W];
        //레이저 연결 위치 및 지도 정보 저장
        for(int i=0;i<H;i++){
            String str = br.readLine();
            for(int j=0;j<W;j++){
                map[i][j] = str.charAt(j);
                if(map[i][j]=='C'){
                    C.add(new position(j,i));
                }
            }
        }
        map[C.get(1).y][C.get(1).x] = '.';	//연결 위치 '.'으로 변경
        int result = bfs(C.get(0), C.get(1));	//BFS 탐색 시작
        bw.write(result + "\n");	//최소 거울 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //다익스트라 알고리즘으로 BFS탐색을 진행하여 최소 거울 개수로 레이저 연결하는 함수
    static int bfs(position start, position end){
        PriorityQueue<laser> pq = new PriorityQueue<>();	//다익스트라에 사용될 우선순위 큐
        int[][][] visited = new int[H][W][4];	//해당 지도에 연결된 최소 거울 개수
        for(int i=0;i<H;i++)	//거울 개수 나올 수 있는 최대값으로 설정
            for(int j=0;j<W;j++)
                Arrays.fill(visited[i][j],10001);
        pq.add(new laser(start.x, start.y, -1, -1));
        while(!pq.isEmpty()){
            laser cur = pq.poll();
            int x = cur.x;
            int y = cur.y;
            int mirror = cur.mirror;
            int direction = cur.direction;
            if(x==end.x && y==end.y)	//레이저 연결 완료!
                return mirror;
            for(int i=0;i<4;i++){
                int tempX = x + dx[i];
                int tempY = y + dy[i];
                if(tempX>=0 && tempY>=0 && tempX<W && tempY < H ){
                    if(map[tempY][tempX] == '.'){
                        //거울을 설치한 경우
                        if(direction != i && visited[tempY][tempX][i] > mirror+1){
                            pq.add(new laser(tempX,tempY,mirror+1, i));
                            visited[tempY][tempX][i] = mirror+1;
                        }
                        //기존 방향으로 레이저가 나아갈 경우
                        else if(direction==i && visited[tempY][tempX][i] > mirror){
                            pq.add(new laser(tempX,tempY,mirror,i));
                            visited[tempY][tempX][i] = mirror;
                        }
                    }
                }
            }
        }
        return 0;		//연결 불가능시
    }
}