[백준] code.plus(BFS 알고리즘,JAVA)16954번, 움직이는 미로 탈출

문제 링크

16954번: 움직이는 미로 탈출

---

주의사항

• 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. 캐릭터가 한 번이동하면 벽은 한 칸 아래로 내려옵니다.

3. 캐릭터가 이동 후 그 자리에 벽이 내려오면 해당 캐릭터는 더 이상 움직일 수 없습니다.

4. 벽이 마지막 행에서 내려갈 때에는 없어집니다.

5. 캐릭터가 왼쪽 최하단에서 오른쪽 최상단으로 갈 수 있는지 결과를 출력해야 합니다.

 

맵에 따른 현재 캐릭터가 위치할 수 있는 공간에서 BFS탐색하고 벽을 1칸 내려주고 다시 탐색하는 방식으로 구현하였습니다.

 

출발지(왼쪽 최하단) : (7, 0)

목적지(오른쪽 최상단) : (0, 7)

 

출발지부터 탐색을 시작하여 목적지에 도착하면 1, 도착하지 못하면 0을 결과로 출력하였습니다.

 

이 문제에서 캐릭터는 상하좌우뿐만 아니라 대각선도 이동이 가능하기 때문에 좌표 변경값을 아래와 같이 주었습니다.

 

dx[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1}

 

dy[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1}

 

(-1, -1)	(0, -1)	(1, -1)
(-1, 0)	(0, 0) , 캐릭터 현재 위치	(1, 0)
(-1, 1)	(0, 1)	(1, 1)

 

 

예제입력 3.

.	.	.	.	.	.	.	. (목적지)
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	#	.	.	.	.	.	.
#	.	.	.	.	.	.	.
. (캐릭터)	#	.	.	.	.	.	.

 

현재 지도 상태에서 출발지점부터 BFS탐색을 통해 진행

.	.	.	.	.	.	.	.(목적지)
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	#	.	.	.	.	.	.
#	. (캐릭터)	.	.	.	.	.	.
. (캐릭터)	#	.	.	.	.	.	.

 

벽 한 칸씩 내려가기 진행

.	.	.	.	.	.	.	.(목적지)
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	#(캐릭터)	.	.	.	.	.	.
#(캐릭터)	.	.	.	.	.	.	.

캐릭터의 위치가 모두 벽이어서 캐릭터들 위치에서 더이상 BFS 탐색을 진행하지 못하기 때문에 목적지까지 도착하지 못한다.

 

결과로 0을 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 체스판에 대한 값을 저장하였습니다.
• 시작지점에서 BFS탐색으로 목적지 도달여부 확인하는 bfs함수를 실행하였습니다.
• 목적지 도달여부를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 체스판에 이동 전 갈 수 있는 캐릭터에 위치에서 BFS 탐색을 진행합니다.
• bfs함수는 목적지에 도달하지 못하면 0, 도달시 1을 반환한다.
• bfs함수는 현재 캐릭터들의 이동을 마친 뒤 wallDrop함수를 실행하여 체스판을 변경합니다.
• wallDrop함수는 체스판에 벽들을 1칸 씩 아래로 내립니다.

 

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;
        }
    }
    static char[][] board = new char[8][8];		//체스판 저장 배열
    static int[] dx = {-1, 0, 1, -1, 0, 1, -1, 0, 1};	//캐릭터 이동 X값 변경값
    static int[] dy = {-1, -1, -1, 0, 0, 0, 1, 1, 1};	//캐릭터 이동 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
        
        //체스판 입력 저장
        for(int i=0;i<8;i++){
            String str = br.readLine();
            for(int j=0;j<8;j++){
                board[i][j] = str.charAt(j);
            }
        }
        int result = bfs();		//출발 지점에서 캐릭터 이동하는 BFS 함수 실행
        bw.write(result + "\n");	//도달 여부 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //출발지점에서 캐릭터 BFS 탐색하는 함수
    static int bfs(){
        Queue<position> queue = new LinkedList<>();
        queue.add(new position(0, 7));		//출발 지점 Queue 저장
        while(!queue.isEmpty()){
            int size = queue.size();
            //현재 체스판 상태에서 Queue에 저장된 캐릭터들을 BFS 탐색
            for(int i=0;i<size;i++){
                position cur = queue.poll();
                int x = cur.x;
                int y = cur.y;
                if(board[y][x] == '#')		//현재 캐릭터가 벽이 되었을 경우
                    continue;
                if(y==0 && x == 7)	//목적지 도착시 도달 확인 1 반환
                    return 1;
                for(int j=0;j<9;j++){
                    int tempX = x + dx[j];
                    int tempY = y + dy[j];
                    if(tempX>=0 && tempY>=0 && tempX<8 && tempY<8){
                        if(board[tempY][tempX]=='.')
                            queue.add(new position(tempX,tempY));
                    }
                }
            }
            wallDrop();		//체스판에 벽 한 칸씩 내리기
        }
        return 0;		//목적지 도달하지 못했을 경우 0 반환
    }
    //체스판에 벽을 1칸씩 내리는 함수
    static void wallDrop(){
    	//한 칸씩 내리기
        for(int i=6;i>=0;i--){
            for(int j=0;j<8;j++){
                board[i+1][j] = board[i][j];
            }
        }
        //첫번째 행은 모두 '.'으로 변경
        for(int i=0;i<8;i++){
            board[0][i] = '.';
        }
    }
}