[백준,BOJ 2178] 미로 탐색(JAVA 구현,추가풀이)

 

-내 생각

  알고리즘 공부를 시작하고 코딩 테스트에서 자주 나온다는 최단경로 문제를 처음으로 풀어보았는데.. 이전에 여러 글들을 보면서 최단거리 문제의 경우에는 BFS만을 이용해서 풀 수 있다고 알고 있었기 때문에 BFS를 사용하려고 했지만, 어떻게 구현해야 할지 감이 잡히지 않았다. 기본적인 흐름은 앞선 DFS문제들과 마찬가지로 인접한 좌표를 탐색하는 것부터 시작해야 한다고 생각했고, 각 경로마다 이동할 때마다 카운트해주어서 분기점에서 갈라진 경로마다의 카운트 변수를 비교해 최솟값을 찾으려고 했는데, 이것도 생각만 했지 구현도 완벽하게 하지 못했다. 2시간 정도 고민해보고 도저히 안될 것 같아 다른 여러 블로그들을 참고했는데, 

하단의 Idgeao99님 블로그에서 힌트를 얻을 수 있었다. 혹시라도 막히는 분들은 참고하시면 좋을 것 같다.

https://ldgeao99.tistory.com/400?category=864321

챕터6-5. 그래프 | 문제풀이(2) - 플러드필 알고리즘(DFS, BFS 탐색응용)

 

  또 다른 문제점이 하나 더 있었는데, BFS를 구현할 때 큐를 사용해야 하는데, 큐에 어떻게 좌표값을 저장할까 였는데, 처음에는 ArrayList에 담아 ArrayList를 큐에 넣을 생각을 했었는데, 바보 같은 생각이었고 그냥 클래스를 하나 만들어 객체를 큐에 저장하면 됐다.... ㅋㅋㅋ

-해법

  Idgeao99님 블로그에서 얻은 힌트는 각 원소를 방문했는지 여부를 체크하는 체크 배열에 해당 배열까지 이동한 경로를 저장한 후 마지막 배열의 원소를 출력해주면 되는 것이었다. 이 방법을 보고 무작정 공백큐가 될 때까지 반복할 때마다 카운트를 해주었더니 정답이 아닌 경로로 이동해도 카운트가 돼버리는 문제점이 있어 조금 고민해보니 그 답이 나왔다. 아래 코드를 보면서 이해해보자.

 

import java.util.*;


class xy{ //xy좌표 저장 클래스
	int x;
	int y;
	
	public xy(int x,int y) {
		this.x= x;
		this.y =y;
	}
}

public class Main {
	static int node[][]; // 2차원 미로 배열
	static int check[][]; // 2차원 방문여부 배열
	static int cnt =1; // 시작점인 (1,1)은 카운트된 상태로 시작하기 때문에 1로 초기화
	static int n,m;
	
	
	public static void bfs(int a,int b) { //BFS메소드
		Queue<xy> queue = new LinkedList<>(); // 큐
		a-=1; // 시작점이 1,1로 들어오므로 -1한 상태를 저장해준다.
		b-=1;
		check[a][b]= cnt; // 초기 cnt변수 값을 방문배열에서 시작점에 저장한다.
		
		queue.offer(new xy(a,b)); // 시작점의 객체를 큐에 삽입
		while(!queue.isEmpty()) { // 이제 큐가 공백이 될 때 까지 반복한다.
			int x = queue.peek().x; // 큐에 저장되어 있는 객체에서 x,y좌표를 저장
			int y = queue.peek().y;
			queue.poll(); // 큐에서 peek후 저장한 것이기 때문에 별도이 poll()수행으로 해당 객체 소멸
			
					//아래의 조건문은 DFS게시글에서 사용한 조건문과 동일
                    //다른분들은 별도의 2개 배열로 동,서,남,북을 탐색하는 방법을 사용하는데 
                    //나중에 시간을 내어 분석 해봐야겠다.
					if(y<node[x].length-1&&node[x][y]==1&&node[x][y+1]==1 && check[x][y+1]==0) {
						check[x][y+1]=check[x][y]+1; // 현재 점이 가지고 있는 경로값을 인접한 점의 방문배열에 저장 
						queue.offer(new xy(x,y+1)); // 인접한 점을 큐에 넣어준다.
					//아래는 모두 이와 동일
					}
					 if(x<node.length-1&&node[x][y]==1&&node[x+1][y]==1 && check[x+1][y]==0) {
						check[x+1][y]=check[x][y]+1;
						
						queue.offer(new xy(x+1,y));
						
					}  if(x>0&&node[x][y]==1&&node[x-1][y]==1 && check[x-1][y]==0) {
						check[x-1][y]=check[x][y]+1;
						
						queue.offer(new xy(x-1,y));
						
					}
					 if(y>0&&node[x][y]==1&&node[x][y-1]==1 && check[x][y-1]==0) {
						check[x][y-1]=check[x][y]+1;
						queue.offer(new xy(x,y-1));
						
					}
					 
					
					 
					
				}
			
			
		
		
	}
			
			
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		
		 n = sc.nextInt();
		 m = sc.nextInt();
		node = new int [n][m];
		check = new int[n][m];
		for(int i=0;i<n;i++) { // 줄단위로 입력이 이루어질 때 값을 저장하는 방식
			String row = sc.next();
			for(int j=0;j<m;j++) {
				
				node[i][j] = row.charAt(j)-'0';
			}
		}
		
		
		
		bfs(1,1); // 시작점 전달
		
		System.out.println(check[n-1][m-1]); // 방문배열의 마지막 원소 즉, 도착지점의 값을 반환하면 
        									// 그것이 최단경로가 된다.
		
		
		
	}
	
}

 

---

  이전에 풀었던 방식과 유사하게 BFS를 이용해 풀었지만, 코드 자체가 많이 간결해졌다. 개념은 위와 동일하다.

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

class Dot{ // 좌표 저장 클래스
		int x;
		int y;
		
		public Dot(int x, int y) { 
			super();
			this.x = x;
			this.y = y;
		}
		
		public int getX() {
			return x;
		}
		public void setX(int x) {
			this.x = x;
		}
		public int getY() {
			return y;
		}
		public void setY(int y) {
			this.y = y;
		}				
}

class Main {
  
  	static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
    
    // BFS 메소드
	static void bfs(int[][] a, int[][] check, Dot d) {
		Queue<Dot> q = new LinkedList<>(); // BFS를 위한 큐 객체
				
		q.offer(d); // 초기 0,0 좌표를 큐에 삽입
		check[d.getX()][d.getY()] = 1; // 초기 출발 위치는 고정이며 1로 시작
		
		while(!q.isEmpty()) { // 주변에 1이 없을 때 까지 반복한다.
			Dot d_p = q.poll();
			int x = d_p.getX();
			int y = d_p.getY();
						
			for(int i=0;i<4;i++) { // 상, 하, 좌, 우 탐색 반복문
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx>=a.length || nx<0 || ny>=a[nx].length || ny < 0) continue;
				
				if(a[nx][ny] == 0) continue; // 0인 좌표는 무시한다.
				
                // 체크 배열에 초기화 된 값과 동일하면 방문하지 않았단 뜻이며, 그곳에 값이 1로 갈 수 있는 경로라면
				if( check[nx][ny] == Integer.MAX_VALUE && a[nx][ny] == 1){					
                	// 해당 체크 배열에 저장되어 있는 경로의 수와 현재 좌표에서 +1 했을 때의 경로의 수 중 최솟값을 저장
					check[nx][ny] = Math.min(check[x][y]+1,check[nx][ny]);
                    // 해당 좌표를 큐에 삽입 후 BFS 탐색 반복
					q.offer(new Dot(nx,ny));
				}
			}			
		}		
	}
	
	public static void main(String[] args)  {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt(); // 행
		int m = in.nextInt(); // 열
		
		int map[][] = new int[n][m]; // 데이터 저장 맵
		int check[][] = new int [n][m]; // 방문 여부 체크 배열
		
		for(int i =0;i<map.length;i++) { // 데이터 입력
			String str = in.next();
			for(int j =0;j<map[i].length;j++) {
				map[i][j] = str.charAt(j)-'0';
			}
		}
        
		for(int i =0;i<check.length;i++) { // int 형 체크 형 배열 초기화
        	// 최단 경로를 찾는 것이기 때문에 비교를 위해 초기값은 MAX_VALUE를 사용했다.
			Arrays.fill(check[i],Integer.MAX_VALUE);
		}
		
		Dot d = new Dot(0,0); // 초기 출발 위치 객체 생성
		bfs(map,check,d); // BFS 수행
		
		System.out.println(check[n-1][m-1]); // 마지막 도착지의 체크 배열에 저장되어 있는 최단 경로 출력
			
	  }
}