[실버1] 2178. 미로 탐색 (Java)

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 BFS 문제를 드디어 도전 해봅니다!!!

---

※  문제를 요약하면 아래와 같습니다.

▶ N x M 크기의 미로가 배열 형태로 주어짐

▶ 배열의 원소들(미로)은 0과 1로 이루어져 있으며 상,하,좌,우 방향으로 1로만 이동이 가능.

▶ (1,1) 부터 (N,M) 까지 가는 경로의 최단 길이 탐색. (시작 칸과 끝 칸 포함)

▶ 위의 조건에 따라서 입력은 맨 첫줄에 N, M 을 입력 받고, 그 다음 라인부터 N x M 크기만큼 미로의 값들을 입력.

▶ (1,1) 부터 (N, M) 까지 가는 최단 경로 수 출력

◈ Input - 1

4 6
101111
101010
101011
111011

◈ Output - 1

15

◈ Input - 2 ( 드럽다 진짜.. )

2 25
1011101110111011101110111
1110111011101110111011101

◈ Output - 2

38

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 미로 값 저장 배열은 boolean 형 배열로 선언 (원소가 0과 1로 구성) 

▶ 탐색 여부 체크 배열 또한 boolean 형 배열로 선언

▶ 북,동,남,서 순서로 탐색 방향 설정

▶ Row, Col 의 좌표 및 지나간 경로의 갯수를 멤버변수로 설정한 MazeInform 클래스 선언

▶ BFS를 위한 큐 자료형 선언. ( 큐의 FIFO 성질을 활용, 1일 경우 In, 0일 경우 Out )

▶탐색 시 인덱스 범위 밖이거나 이미 탐색한 인덱스의 경우 Out

▶ 마지막 방 번호 도달 시 최소값 비교를 하여 min 변수에 결과 저장.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


class MazeInform {
	int nRow;
	int nCol;
	int nCount;
	
	public MazeInform(int nRow, int nCol, int nCount) {
		this.nRow = nRow;
		this.nCol = nCol;
		this.nCount = nCount;
	}
}

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		int nMin = 9999999;
		
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bReader.readLine());
		
        int nRows = Integer.parseInt(st.nextToken());
        int nCols = Integer.parseInt(st.nextToken());
        
        // 미로 값 저장 배열, 탐색 여부 저장 배열.
        boolean[][] barrMaze = new boolean[nRows][nCols];
        boolean[][] bIsSearched = new boolean[nRows][nCols];
        
        // 미로 값 저장.
        for(int i = 0; i < nRows; i++) {
        	String strTemp = bReader.readLine();
        	for(int j = 0; j < nCols; j++) {
        		if(strTemp.charAt(j) == '1')
        			barrMaze[i][j] = true;
        		else
        			barrMaze[i][j] = false;
        	}
        }
        
        // 북, 동, 남, 서
        int[] dr = {1, 0, -1, 0};
        int[] dc = {0, 1, 0, -1};
        
        // BFS를 위한 큐 + (0,0)은 반드시 1 (문제에서의 (1,1))
        Queue<MazeInform> qBuffer = new LinkedList<>();
        bIsSearched[0][0] = true;
        qBuffer.add(new MazeInform(0, 0, 1));
        
        // BFS
        while(!qBuffer.isEmpty()) {
        	MazeInform mazeTemp = qBuffer.poll();
        	for(int k = 0; k < dr.length; k++) {
        		// 방향 탐색.
        		int nRowPoint = mazeTemp.nRow + dr[k];
        		int nColPoint = mazeTemp.nCol + dc[k];
        		int nCount = mazeTemp.nCount;

        		if(nRowPoint < 0 || nRowPoint >= nRows || nColPoint < 0 || nColPoint >= nCols ||
        				bIsSearched[nRowPoint][nColPoint])
        			continue;
        		
        		bIsSearched[nRowPoint][nColPoint] = true;
        		
        		// 다음 방향이 1이면 이동, qBuffer에 저장.
        		if(barrMaze[nRowPoint][nColPoint]) {
        			nCount++;
        			qBuffer.add(new MazeInform(nRowPoint, nColPoint, nCount));
        		}
        		
        		// 도착 했을 경우, 최소값 비교 ( 최소 경로 )
        		if(nRowPoint == nRows-1 && nColPoint == nCols-1 && nMin > nCount)
        			nMin = nCount;
        		
        	}
        }
        System.out.println(nMin);   
	}
}

 이론을 하나씩 하나씩 점검해보면서 구현 전에 설계해보구 코드를 작성하니 정~~~~말 시간이 오래걸리네요. 심지어 이제 좀 어떤지 알 것 같은 느낌이라 앞으로도 bfs문제를 조금 더 풀어봐야 확실히 알 것 같습니다. 알고리즘 정말 쉽지 않네요. 

긴 글 읽어주셔서 감사합니다!

Good Luck! (피드백 고맙습니다)