[BFS] BOJ 2178번, 미로탐색 (JAVA)

미로 탐색

문제

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

---

1. 주어진 배열에서 특정 조건을 만족할때 이동하는 경로의 최소값을 구하는 문제 유형

 

문제에서는 배열이 이동할 수 있는 경우는 값이 1일 때 이다

 

이러한 문제유형은

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

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

for(int i=0;i<4;i++)

다음과 같이 4방향 배열을 만들고 각각의 경우를 범위와 값을 비교하면서 탐색해 주면된다.

 

그리고 새로운 dist 배열에 이동할때마다 증가하는 값을 저장해서 dist[n-1][m-1] 위치의 값을 출력해 주었다.

 

---

import java.util.*;
import java.io.*;
class Main{
	static int n, m;
	static int result;
	static int[][] arr;
	static int[][] dist;
	
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		arr = new int[n][m];
		dist = new int[n][m];
		for(int i=0;i<n;i++)
		{
			String s = br.readLine();
			for(int j=0;j<m;j++)
			{
				int k = s.charAt(i) - '0';
				arr[i][j] = k;
			}
		}
		
		bfs(0,0);
		
		System.out.println(dist[n-1][m-1]);
	}
	public static void bfs(int y, int x)
	{
		Queue<Pos> q = new LinkedList<>();
		q.add(new Pos(y,x));
		dist[y][x] = 1;
		
		while(!q.isEmpty())
		{
			Pos now = q. poll();
			for(int i=0;i<4;i++)
			{
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];
				
				if(nx >= 0 && ny >=0 && nx < m && ny < n)
				{
					if(dist[ny][nx] == 0 && arr[ny][nx] == 1)
					{
						dist[ny][nx] = dist[now.y][now.x] + 1;
						q.add(new Pos(ny,nx));
					}
				}
			}
		}
	}
}
class Pos{
	int y, x;
	public Pos(int y, int x)
	{
		this.y = y;
		this.x = x;
	}
}