JAVA 미로탐색 / BFS

 

 

😒 BFS / Breadth-First Search / 너비 우선 탐색 

 

너비 우선 탐색 : 

    하나의 정점에서 시작해서 차례로 모든 정점을 방문하게 된다. 

 

    따라서 특정 도시에서 다른 도시로 가거나, 미로의 최단 거리를 찾거나,

 

 

보통은 두 좌표 사이의 ( 노드 사이의 ) 최단 경로 혹은 임의 경로를 찾기 위해 쓴다. 

 

🥕 구현 시, 특정 좌표 ( 노드 ) 를 방문한것에 대한 여부를 반드시 검사해야 한다. 

 

    검사하지 않는다면 무한 루프에 빠질 위험이 존재한다. 

 

방문한 노드를  차례로 꺼낼 수 있는 자료 구조인 Queue 를 사용. 즉 선입선출이 원칙이다.

 

 

🥕 왜 최단 거리가 되는가 ? 

 

https://wikidocs.net/125662 참조 : 

 

https://wikidocs.net/125662

미로탐색과 같은 문제를 BFS를 구현하다보면, 누구나 한 번씩은 의구심을 갖게 됩니다. 계속해서 visited를 통해 경로를 찍어 보면서도, "이 경로가 정말 최적 경로가 맞을까?" 또는 "혹시 다른 경로를 통해서 가면 최소값을 갖게 되는 경우의 수가 생길 수 도 있지 않을까?" 같은 의문이 들게 됩니다. 천천히 생각해 보겠습니다. 가장 먼저 시작점에 준하는 좌표의 visited 배열에는 출발지를 뜻하는 1을 표기하게 됩니다. 그리고 두 번 째로 갈 수 있는 모든 경로에는 2가, 세 번만에 도달이 가능한 곳에는 모두 3이 표기됩니다. 이렇게 vistied배열에는 모든 순간 갈 수 있는 최선의 경우의 수가 기입되는 것이지요. 다른 말로 표현해보면, 내가 이번에 탐색해서 발견한 노드가 이미 이전에 방문한 노드라면, 기존에 채워진 값은 새로 채우려는 값보다 항상 작거나 같을 수 밖에 없다는 뜻 입니다. 따라서 우리는 해당 노드의 방문 여부(if(visited[i][j]==0)) 만 확인하게 되는 것이지요.

 

물결의 파동에 비유한 설명도 있다.

동시에 다른 노드를 계속해서 채워가고, 채워 간 곳은 방문했다는 기록을 남기기 때문에.

 

 

구현 : 

 

 

// 클래스로 담아서 쓴다. 
class Location { 
    int row;
    int col;
    int dist;
    public Location(int row, int col, int dist) {
        this.row = row;
        this.col = col;
        this.dist = dist;
    }
}


////  좌우 상하 간격과 미로를 담을 배열 그리고 방문 여부 체크 배열

static int charNums;
static int linkNums;
static String arr[][];
static boolean[][] visited;

////

public static void main(String[] args) {

    maze();

    chk = new int[lineNums][charNums];
    visited = new boolean[lineNums][charNums];
	
    // 시작점은 방문하고, 
    visited[1][0] = true;
    // A 좌표부터 출발한다.
    int answer = findPath(1,0);

    System.out.println(" 정답 : " + answer);
}




public static int findPath(int x, int y) {

        Queue<Location> queue = new LinkedList<>();

        int[] xArr = {0,0,-1,1,};
        int[] yArr = {-1,1,0,0,};

        queue.add(new Location(x,y,1));
        visited[x][y] = true;
        while(!queue.isEmpty()) {
            Location location = queue.poll();

            int row = location.row;
            int col = location.col;
            int dist = location.dist;

			// 목적지는 'B' 이다 
            if (arr[row][col].equals("B")) {
                System.out.println(" 도착 : " + arr[row][col]);
                return dist;
            }

            for (int i = 0; i < 4; i ++ ) {
                // 상하좌우 배열을 통해 상하좌우 위치를 모두 찾는다.
                int nextX =  row + xArr[i];
                int nextY =  col + yArr[i];

				//방문했는가? 방문할수있는가?
                if (checkLocation(nextX,nextY) && !visited[nextX][nextY]) {
                    
                    // 하, 우  모두 방문 가능하다면, 
                    // 큐에는 2개의 방향이 동시에 들어간다.
                    queue.add(new Location(nextX, nextY, dist+1));
                    
                    // 방문 기록.
                    visited[nextX][nextY] = true;
                }

            }
        }

        return 0;
    }

 

방문 체크.

  // 방문 여부 체크 
  public static boolean checkLocation (int nextX, int nextY) {

        if (nextX < 0 || nextX >= charNums || nextY < 0 || nextY >= lineNums || arr[nextX][nextY].equals("0")) {
            return false;
        }
        return true;
  }

 

 

미로 :

     0은 못지나간다.

 

미로 배열 : 


      String mazes =
                "0000000000000000000000000000000000000000000000000000000000000000\n" +
                "A             000                                            000\n" +
                "0000000000000 000 000000000000000000 00 0000000000000000000 00 0\n" +
                "0        0 00 0                   00 00 0   00     0      0  0 0\n" +
                "0000 000 0 00 0 00000000000000000 00 00 000  00 00 0 0000 00 0 0\n" +
                "0    0 0 0 00 0  0000           0 00 00 0000000000 0 0000000 0 0\n" +
                "0 00 0 0 0 00 0       000000000 0 00 00            0 0       0 0\n" +
                "0           0 0000 0 0       0 000000000000 0 000000 00000000000\n" +
                "0 00000000000   0  0 0 0000000              0 0                0\n" +
                "0      0000   0 0 00 000000  0000000000000000 000000 000000000 0\n" +
                "0 0000     00                                                0 B\n" +
                "0000000000000000000000000000000000000000000000000000000000000000";