[BAEKJOON 백준] 2178 미로 탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

 

BFS를 이용을 해서 미로를 탐색하는 방식으로 문제를 풀었다.

BFS에서 Queue를 이용을 해서 각 각의 위치를 넣어주고, 목적지에 도착을 하면 탐색을 끝내는 방식이다.

그리고 4방탐색을 위해 point 클래스를 만들어서 탐색을 하게 했다.

 

그리고 visit 배열을 만들어서 한번 간곳이나 0인 곳을 안가도록 만들어 돌아가는 일이 없도록 하고, 그렇게 만들어진 결과값을 출력해 준다.

 

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

public class Main {
	static class point{
		int x,y;

		public point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine()," ");
		
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		int arr[][]=new int[N][M];
		int visitcnt[][]=new int[N][M];
		boolean visit[][]=new boolean[N][M];
		for(int i=0;i<N;i++) {
			String s=bf.readLine();
			for(int j=0;j<M;j++) {
				arr[i][j]=s.charAt(j)-'0';
					
//				System.out.print(arr[i][j]+" ");
			}
//			System.out.println();
		}
		LinkedList <point> que=new LinkedList<>();
		que.offer(new point(0,0));
		visit[0][0]=true;
		visitcnt[0][0]=1;


		while(!que.isEmpty()) {
			int size=que.size();
//			for(int i=0;i<size;i++) {
				point p=que.poll();
				for(int k=0;k<4;k++) {
					int nx=p.x+dx[k];
					int ny=p.y+dy[k];
					if(nx>=0&&nx<N&&ny>=0&&ny<M&&arr[nx][ny]==1&&!visit[nx][ny]) {
						que.offer(new point(nx,ny));
						visit[nx][ny]=true;
						visitcnt[nx][ny]=visitcnt[p.x][p.y]+1;
					}
				}
//			}

			
		}
		System.out.println(visitcnt[N-1][M-1]);
	}

}