[백준 2178] 미로 탐색 (JAVA)

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

2178번: 미로 탐색

 

문제 이름에서부터 알수 있듯 단순한 탐색문제이다.

여러 탐색 알고리즘 중 BFS를 적용해서 풀어보도록 하겠다.

 

우선 문제 분석을 해보자면 0과 1로만 이루어진 행렬로 미로의 구조가 주어진다.

1일때만 진행이 가능하고 0일때는 진행이 불가할때

왼쪽 최상단 지점에서 오른쪽 최하단까지의 최단거리를 구하는 문제이다.

 

한번에 한칸씩 이동이 가능하고 상하좌우로 이동이 가능하며, 총 이동 칸수 == 최단거리 를 구하면 되는것이다.

 

우선 한번에 이동이 가능한 방향은 상하좌우 4가지뿐이기 때문에 너비를 4라고 생각하겠다.

이를 반복문으로 수행하기 위해서 상하좌우 좌표에 대해 표현할 배열 dx, dy를 생성해준다.

 

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

 

 

다음으로는 BFS 알고리즘을 위해 사용할 큐, 현재 미로에 대한 정보를 입력받을 배열,

그리고 방문처리와 최단거리에 대해 저장할 배열을 선언해준다.

이때 큐에 저장할 정점은 좌표이므로 Java의 awt 패키지의 Point 클래스를 사용한 배열로 만들어 주도록 하겠다.

 

	static int n,m,front,rear,vLen;
	static Point[] queue;
	static char[][] metrix;
	static int[][]cnt; // 방문처리 & 최단경로

 

실제 입력받은 데이터에 따라 동적으로 자원을 할당해줄 메소드도 하나 만들어준다.

 

	static void setting() {
		vLen = n*m;
		metrix = new char[n + 1][m + 1];
		queue = new Point[vLen];
		cnt = new int[n + 1][m + 1];
	}

 

 

이제 BFS 알고리즘을 적용해 문제를 풀어보겠다.

탐색을 시작할 최초의 좌표를 인자로 받아 큐에 삽입 후,

방문처리와 시작지점의 최단거리를 입력한다.

 

이때 cnt 배열은 0일땐 미방문 , 0이 아닐땐 방문한것으로 간주하고

실제 배열에 존재하는 값은 해당 좌표까지의 최단거리를 의미한다.

 

	static void bfs(int sx, int sy) {
		queue[rear++] = new Point(sx,sy);
		cnt[sx][sy]++;
	}

 

탐색을 진행하기전 현재 정점을 확인해야 하므로 큐에서 정점을 꺼내 변수에 저장해준뒤

이전에 생정한 dx, dy 배열을 사용해 순회한다.

 

현재 정점에서 이동가능한 상하좌우 좌표에 대해

미로에서 벗어나지 않으면서 방문처리가 되어있지 않으면서 미로의 값이 1인 경우에 대해서만

큐에 삽입을 해주고 방문처리후 최단거리를 갱신한다.

 

	static void bfs(int sx, int sy) {
		queue[rear++] = new Point(sx,sy);
		cnt[sx][sy]++;
        
		Point node = queue[front];
		queue[front++] = null;
		front%=vLen;
        
		for(int i = 0; i < 4; i++) {
			int x = node.x + dx[i];
			int y = node.y + dy[i];
			if(x > 0 && x <= n && y > 0 && y <= m && cnt[x][y] == 0 && metrix[x][y] == '1') {
				queue[rear++] = new Point(x,y);
				rear%=vLen;
                // 각 정점당 한번씩만 갱신된다 최단거리가 아닌경우 이미 방문처리가 되어있어 갱신될수 없음
				cnt[x][y] = cnt[node.x][node.y] + 1; 
			}
		}
	}

 

 

이제 반복처리이다.

반복의 종료 시점은 목표 지점인 (n,m)에 대한 방문처리가 이루어졌거나, 큐가 모두 비워진 시점이다.

 

 

	static void bfs(int sx, int sy) {
		queue[rear++] = new Point(sx,sy);
		cnt[sx][sy]++;
        
		while(queue[front] != null && cnt[n][m] == 0) { // 큐가 비워진경우
			
            		Point node = queue[front];
			queue[front++] = null;
			front%=vLen;
            
			for(int i = 0; i < 4; i++) {
				int x = node.x + dx[i];
				int y = node.y + dy[i];
				if(x > 0 && x <= n && y > 0 && y <= m && cnt[x][y] == 0 && metrix[x][y] == '1') {
					queue[rear++] = new Point(x,y);
					rear%=vLen;
					cnt[x][y] = cnt[node.x][node.y] + 1;
				}
			}
		}
	}

 

 

이제 입출력 대한 소스만 작성후 프로그램을 실행시켜보면,

 

 

주어진 예제에 대해서 정상적으로 실행되는것을 확인 할 수 있다.

 

아래는 코드의 전문이다.

 

package boj2;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj2178 {
	
	static int n,m,front,rear,vLen;
	static Point[] queue;
	static char[][] metrix;
	static int[][]cnt;
	
	static int[] dx = { 1 , 0 , -1 , 0};
	static int[] dy = { 0 , 1 , 0 , -1};
	
	static void setting() {
		vLen = n*m;
		metrix = new char[n + 1][m + 1];
		queue = new Point[vLen];
		cnt = new int[n + 1][m + 1];
	}
	
	static void bfs(int sx, int sy) {
		queue[rear++] = new Point(sx,sy);
		cnt[sx][sy]++;
		while(queue[front] != null && cnt[n][m] == 0) { // 큐가 비워진경우
			Point node = queue[front];
			queue[front++] = null;
			front%=vLen;
			for(int i = 0; i < 4; i++) {
				int x = node.x + dx[i];
				int y = node.y + dy[i];
				if(x > 0 && x <= n && y > 0 && y <= m && cnt[x][y] == 0 && metrix[x][y] == '1') {
					queue[rear++] = new Point(x,y);
					rear%=vLen;
					cnt[x][y] = cnt[node.x][node.y] + 1; // 각 정점당 한번씩만 갱신된다 최단거리가 아닌경우 이미 방문처리가 되어있어 갱신될수 없음
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		setting();
		
		for(int i = 0; i < n; i++) {
			String input = in.readLine();
			for(int j = 0; j < m; j++) {
				metrix[i + 1][j + 1] = input.charAt(j);
			}
		}
		
		in.close();
		
		bfs(1,1);
		
		System.out.print(cnt[n][m]);
		
	}
	

}