백준 2178 미로탐색(자바)

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

2178번: 미로 탐색

 

BFS의 대표적인 문제다.

1주일 전에 풀었는데 다시 풀려니깐 생각이 안나고 다시 코드를 찾아보게 돼서 정리하고자 한다.

 

미로는 배열의 처음부터 시작하고 N,M에 도착하면 끝난다.

그 중에서 가장 최단 거리로 이동할 수 있는 방법을 찾아야 한다.

나는 result 배열을 만들어서 구하고자 했다.

 

우선 전체 코드이다.

 

package 단계별문제;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 미로탐색 {
	static int[][] map; // 미로의 맵을 저장
	static int N;
	static int M;
	static boolean[][] visited; // 방문체크
	static int[][] result; // 미로의 결과 저장
	// 상 하 좌 우 탐색
	static int[] dr = { 1, -1, 0, 0 }; 
	static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][M];
		visited = new boolean[N][M];
		result = new int[N][M];
		for (int i = 0; i < N; i++) {
			String str = sc.next();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j)-'0'; // 맵 입력 받기.
			}
		}
		
		BFS(0, 0);
		System.out.println(result[N-1][M-1]); // 결과배열의 마지막을 출력
	}

	// i와 j위치를 받는 BFS메서드를 만든다.
	public static void BFS(int x, int y) {
		Queue<int[]> q = new LinkedList<>(); // int배열을 담을 수 있는 큐를 생성
		q.add(new int[] { x, y }); // 큐에 해당 좌표 값을 배열로 넣어준다.

		result[x][y] = 1; // 해당 좌표의 result 배열을 우선 1로 만들어준다.(거리 1 이동했다는 소리)

		while (!q.isEmpty()) {
			x = q.peek()[0]; // i좌표의 값을 x에 저장한다.
			y = q.peek()[1]; // j좌표의 값을 y에 저장한다.
			visited[x][y] = true; // 너 방문했어! 표시해준다.
			q.poll(); // poll을 이용해 큐를 비워준다.(위에서 x,y에 저장했으니)
			for (int i = 0; i < 4; i++) { // 사방탐색을 위해서
				int idr = dr[i] + x;
				int idc = dc[i] + y;
				// 맵 범위 안에 들어있고
				if (idr >= 0 && idc >= 0 && idr < N && idc < M) {
					// 해당 좌표가 1이고 아직 안들렸다면?
					if (map[idr][idc] == 1 && !visited[idr][idc]) {
						// 우선 result배열에 이전 위치+1을 해준다. 그러면 이전 위치는 1이었으니 2가 저장되고 그 다음에는 3이 저장되고..반복한다.
						result[idr][idc] = result[x][y] + 1;
						// 만약에 끝 지점에 도착했으면
						if(idr==N-1 && idc==M-1) {
							// 방문표시 해주고 return한다.
							visited[idr][idc] = true;
							return;
						}
						// 다시 큐에 해당 좌표를 넣어주고
						q.add(new int[] {idr, idc});
						// 방문 표시를 해준다.
						visited[idr][idc] = true;
					}
				}
			}
		}
	}
}

 

코드를 하나씩 살펴보자.

 

static int[][] map; // 미로의 맵을 저장     
static int N;                        
static int M;                        
static boolean[][] visited; // 방문체크  
static int[][] result; // 미로의 결과 저장  
// 상 하 좌 우 탐색                        
static int[] dr = { 1, -1, 0, 0 };   
static int[] dc = { 0, 0, -1, 1 };

전부 static으로 선언해줬다. (이게 데리고 다니지 않아도 돼서 아직은 편하다)

 

public static void main(String[] args) {                                             
	Scanner sc = new Scanner(System.in);                                             
	N = sc.nextInt();                                                                
	M = sc.nextInt();                                                                
	map = new int[N][M];                                                             
	visited = new boolean[N][M];                                                     
	result = new int[N][M];                                                          
	for (int i = 0; i < N; i++) {                                                    
		String str = sc.next();                                                      
		for (int j = 0; j < M; j++) {                                                
			map[i][j] = str.charAt(j)-'0'; // 맵 입력 받기.                               
		}                                                                            
	}                                                                                
	                                                                                 
	BFS(0, 0);                                                                       
	System.out.println(result[N-1][M-1]); // 결과배열의 마지막을 출력                           
}

메인부다.

입력이 1010001 이렇게 붙어서 들어오기 때문에 String으로 우선 받고

charAt을 이용해 잘라서 넣어줬다.(char이기 때문에 -'0'을 꼭 해줘야 정상 값이 들어간다)

출력은 배열의 가장 마지막을 출력했다.

 

public static void BFS(int x, int y) {                                          
	Queue<int[]> q = new LinkedList<>(); // int배열을 담을 수 있는 큐를 생성                
	q.add(new int[] { x, y }); // 큐에 해당 좌표 값을 배열로 넣어준다.                         
                                                                                
	result[x][y] = 1; // 해당 좌표의 result 배열을 우선 1로 만들어준다.(거리 1 이동했다는 소리)          
                                                                                
	while (!q.isEmpty()) {                                                      
		x = q.peek()[0]; // i좌표의 값을 x에 저장한다.                                    
		y = q.peek()[1]; // j좌표의 값을 y에 저장한다.                                    
		visited[x][y] = true; // 너 방문했어! 표시해준다.                                 
		q.poll(); // poll을 이용해 큐를 비워준다.(위에서 x,y에 저장했으니)

BFS를 돌기 위해 메서드를 만들었다.

매개변수로 x와 y의 위치를 받는다.

우선 BFS라서 큐를 생성하는데 2개의 좌표를 저장해야 하기 때문에 int배열 타입으로 만들었다.

큐에 해당 좌표 값을 배열로 넣어준다.

 

그리고 이동 거리를 result배열에 저장하는데 우선 첫 시작이니 해당 좌표에 1을 넣어준다.

 

이후 큐가 비어있지 않다면 반복을 돌리는데

peek을 이용해서 큐에 넣은 x, y좌표의 값을 꺼내준다.

해당 부분에서 x=q.poll()[0]; y=q.poll()[1];로 계속 사용했더니 널포인터 에러가 나서 찾는 데 시간이 걸렸다.(주의)

이후 방문표시를 해주고 x,y를 갱신했으니 poll로 큐를 비워준다

 

for (int i = 0; i < 4; i++) { // 사방탐색을 위해서                                                            
	int idr = dr[i] + x;                                                                              
	int idc = dc[i] + y;                                                                              
	// 맵 범위 안에 들어있고                                                                                   
	if (idr >= 0 && idc >= 0 && idr < N && idc < M) {                                                 
		// 해당 좌표가 1이고 아직 안들렸다면?                                                                       
		if (map[idr][idc] == 1 && !visited[idr][idc]) {                                               
			// 우선 result배열에 이전 위치+1을 해준다. 그러면 이전 위치는 1이었으니 2가 저장되고 그 다음에는 3이 저장되고..반복한다.              
			result[idr][idc] = result[x][y] + 1;                                                      
			// 만약에 끝 지점에 도착했으면                                                                        
			if(idr==N-1 && idc==M-1) {                                                                
				// 방문표시 해주고 return한다.                                                                 
				visited[idr][idc] = true;                                                             
				return;                                                                               
			}                                                                                         
			// 다시 큐에 해당 좌표를 넣어주고                                                                      
			q.add(new int[] {idr, idc});                                                              
			// 방문 표시를 해준다.                                                                            
			visited[idr][idc] = true;                                                                 
		}                                                                                             
	}                                                                                                 
}

그 다음 사방탐색을 돌려서 해당 위치에 1이 있는지 확인을 해야한다.

먼저 idr, idc를 만들어서 더해주고 맵을 벗어나지 않았는지 확인을 한다.

그리고 해당 좌표가 1로 길이 있고, 아직 방문을 안했는지 확인한다.

 

둘 다 해당되면 result로 해당 배열에 이전 위치 +1로 값을 넣어준다.(이러면 거리가 1씩 더해지며 들어간다)

이렇게 1씩 더해지며 사방으로 퍼지면서 탐색을 진행한다.

만약에 끝에 도달했으면 방문표시만 하고 return을 한다.

 

그리고 큐에 다시 해당 좌표를 넣어주고 방문표시를 해주면 끝난다.