백준 / 2178 / 미로 탐색

문제

 

입력

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

 

출력

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

 

입출력 예

해결

bfs를 이용해 최적의 경로를 파악할 수 있다.

 

코드

	import java.util.Queue;
	import java.util.LinkedList;
	import java.util.Scanner;
	public class miro_bfs {
	// 위치를 좌표로 표현하기 위한 클래스
	public static class Pairs {
	int x;
	int y;
	// 생성자 함수
	Pairs(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}
	// 상하좌우를 움직일 때 사용하는 1차원 배열
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { -1, 1, 0, 0 };
	// 입력 미로
	public static int[][] miro;
	// 지나간 자리인지 확인하기 위한 1차원 배열
	public static boolean[][] check;
	public static void bfs(Pairs i, int h, int w) {
	// 큐 생성 (자료형은 Pairs)
	Queue<Pairs> q = new LinkedList<Pairs>();
	// 시작점을 큐에 삽입
	q.offer(i);
	// 지나갔다고 표시
	check[i.x][i.y] = true;
	// 큐가 빌 때 까지 반복
	while(!q.isEmpty()) {
	// 상위 요소 하나 뺀다
	Pairs temp = q.poll();
	// 만약 목표 지점까지 왔다면 return
	if(temp.x == (h - 1) && temp.y == (w - 1))
	return;
	// 상하좌우 탐색
	for(int j = 0 ; j < dx.length ; j++) {
	// 이동한 좌표값
	int nx = temp.x + dx[j];
	int ny = temp.y + dy[j];
	// 만약 좌표가 제한 범위를 넘어가지 않았다면
	if (0 <= nx && nx < h && 0 <= ny && ny < w) {
	// 만약 건널 수 있는데 아직 지나가지 않았다면
	if(miro[nx][ny] == 1 && check[nx][ny] == false) {
	Pairs n_pair = new Pairs(nx, ny);
	// 이 좌표를 큐에 삽입
	q.offer(n_pair);
	// 값을 이전 좌표 값 + 1로 변경(이걸 이용해 건넌 횟수 파악)
	miro[nx][ny] = miro[temp.x][temp.y] + 1;
	// 지나갔다고 표시
	check[nx][ny] = true;
	}
	}
	}
	}
	}
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int h = sc.nextInt();
	int w = sc.nextInt();
	miro = new int[h][w];
	check = new boolean[h][w];
	for(int i = 0 ; i < h ; i++) {
	String temp = sc.next();
	for(int j = 0 ; j < w ; j++) {
	miro[i][j] = temp.charAt(j) - '0';
	}
	}
	Pairs start = new Pairs(0, 0);
	// bfs 함수 호출
	bfs(start, h, w);
	// 마지막 좌표값 출력
	System.out.println(miro[h-1][w-1]);
	}
	}

view raw index.java hosted with ❤ by GitHub

 

느낀점

bfs를 이용해 탐색하는 기능은 구현했으나 최소로 지날 수 있는 값은 구할 수 없었다. 다른 블로그를 참고해보니 이전 경로의 값에 1을 더해가는 방식으로 해결했다. 그래프에 대한 이해도가 높았다면 풀 수 있는 문제였다..

 

출처

https://ggmouse.tistory.com/315

[JAVA] 백준 알고리즘 2178 : 미로 탐색 (BFS)