N*M 크기의 직사각형 형태의 미로에 갇혀있다.
미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.
현재 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다.
괴물이 있는 부분은 0, 괴물이 없는 부분은 1이다.
입력 예시 :
5 6
101010
111111
000001
111111
111111
출력 예시 :
10
문제 분석
미로를 탈출하는 경로를 찾는 문제인데, 처음에 주어진 입력 예시만 보았을 때는 한 경로를 깊이 탐색하는 DFS를 써야만 한다고 생각했다.
이는 미로를 '탈출'한다는 경로의 관점에서 보아서 잘못 접근한 것이다.
단순히 미로를 탈출하는 것이 아니라, '최단 경로'를 통해 탈출해야 한다.
하나의 경로에 깊숙히 들어갔다가 나와서 다시 다른 경로에 깊숙히 들어가는 것은 최단 경로를 보장하지 않는다.
처음 경로로 깊숙히 들어가서 탈출했다 하더라도, 그 경로는 최단 경로가 아닐 수 있다. 다른 경로가 존재함에도 불구하고 탐색하지 않은 것이다.
대신, 현재 위치에서 갈 수 있는 모든 경로를 한 번에 한 단계씩 차례대로 방문하면서, 이 과정에서 가장 먼저 도착한 경로가 항상 최단경로가 된다. 즉 BFS 알고리즘을 사용해야만 최단 경로를 알 수 있다.
코드 작성
nextInt(): 공백 또는 Enter가 있을 때까지 입력을 받음.
nextLine():
- nextInt()는 정수 입력만을 처리하기 때문에, 입력된 후 남아 있는 **개행 문자(Enter)**는 버퍼에 남음.
- 이 개행 문자를 제거하지 않으면 다음 입력을 받을 때 문제가 발생할 수 있음. 예를 들어, 다음에 nextLine()으로 문자열을 입력받을 때, 바로 이전에 남아 있던 Enter가 자동으로 읽혀질 수 있음.
- 따라서 sc.nextLine();을 사용해 버퍼를 비워주는 것이 일반적인 방법
입력받은 값(문자열)을 숫자로 바꾸기.
graph 배열은 초기에는 0과 1로만 이루어진 배열이지만, 시작점으로부터 끝점까지 가는 최단 경로를 구하기 위해
bfs 탐색을 수행하면서 시작점(1,1)에서 각 지점까지의 거리로 바뀐다.
import java.util.*;
class Node{
private int x;
private int y;
public Node(int x,int y){
this.x=x;
this.y=y;
}
public int getX(){
return this.x;
}
public int getY(){
return this.y;
}
}
public class Main {
public static int n,m;
public static int[][] graph=new int[201][201];
//이동할 네 가지 방향 정의
public static int dx[]={-1,1,0,0};
public static int dy[]={0,0,-1,1};
//상하좌우를 모두 방문하는 bfs.
public static int bfs(int x, int y){
//큐(Queue) 구현을 위해 queue 라이브러리 사용
Queue<Node> q=new LinkedList<>();
//시작 지점인 0,0을 추가
q.offer(new Node(x,y));
//큐가 빌 때까지 반복하기
while(!q.isEmpty()){
//지금 큐에 있는 것 중 가장 먼저 들어온 노드를 반환
Node node=q.poll();
//반환된 노드의 x값
x=node.getX();
//반환된 노드의 y값
y=node.getY();
//현재 위치에서 4가지 방향으로의 위치 확인
for (int i=0; i<4;i++){
//4가지 값중 하나를 더함
int nx=x+dx[i];
//4가지 값중 하나를 더함
int ny=y+dy[i];
//미로 찾기 공간을 벗어난 경우 무시
if(nx<0||nx>=n||ny<0||ny>=m) continue;
//괴물인 경우 무시
if(graph[nx][ny]==0) continue;
//해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if(graph[nx][ny]==1){
//그래프에 있던 1,0들은 bfs탐색을 진행하면서 시작점으로부터 거리로 바뀜
graph[nx][ny]=graph[x][y]+1;
//이 노드에 대한 상하좌우 탐색을 예약하기 위해 큐에 삽입
q.offer(new Node(nx,ny));
}
}
}
//끝점에는 결국 시작점으로부터 끝점까지의 거리가 저장될 것. 그 값이 구하는 값
return graph[n-1][m-1];
}
public static void main(String [] args){
Scanner sc=new Scanner(System.in);
//N,M을 공백을 기준으로 구분하여 입력 받기
n=sc.nextInt();
m=sc.nextInt();
sc.nextLine();//버퍼 지우기
//2차원 리스트의 맵 정보 입력 받기
for (int i=0; i<n; i++){
String str = sc.nextLine();
for (int j=0; j<m; j++){
graph[i][j]=str.charAt(j)-'0';
}
}
//BFS를 수행한 결과 출력, 시작점은 0,0
System.out.println(bfs(0,0));
sc.close();
}
}