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

백준 2178번 문제  - 미로 탐색

2178번: 미로 탐색

---

문제 분석

 

 

• N X M 미로를 입력 받고, 미로의 첫부터 끝까지 이동할 때 최소 이동 횟수를 구해라

 

---

해결 키 포인트

 

• BFS(너비 우선 탐색) 개념 파악 
• 미로에 따른 인접 노드를 어떻게 판단할 것인지 정해야한다.
  • BFS list는 [N][M] 2차 배열 형식으로, 상하좌우로 이동 가능한지 숫자로 삽입한다.
  • ex) 0 = 오른쪽 | 1 = 아래 | 2 = 위 | 3 = 왼쪽
• 한번 count 증가할 때, 큐에 들어있는 모든 노드를 확인한다.
• 큐에 넣기 위해 Node라는 새로운 객체를 생성한다.

---

너비 우선 탐색(BFS)

 

그래프 완전 탐색 기번 중 하나로, 그래프의 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

 

너비 우선 탐색의 핵심 이론

 

• 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요
• 그래프는 인접 리스트로 표현
• DFS의 탐색 방식은 선입 선출 특성을 가짐 ( 큐 사용 )

 

알고리즘

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

 

Do It! 알고리즘 코딩 테스트

 

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입 (이를 모든 정점에 다한다)

 

Do It! 알고리즘 코딩 테스트

 

만약 큐에 노드가 없으면, 방문하지 않은 정점을 알아내, 큐에 삽입하고 다시 2번 단계를 반복한다.

---

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer> [][] list;
    static boolean[][] isChecked;

    static int N, M, count = 0;

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N,M,V 입력
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 확인여부 list | 인접노드를 알려줄 list 생성
        isChecked = new boolean[N][M];

        list = new ArrayList[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                list[i][j] = new ArrayList();
            }
        }

        // 간선 입력 (갈 수 있는 방향 추가 : 0 = 오른쪽 | 1 = 아래 | 2 = 위 | 3 = 왼쪽 )
        for (int i = 0; i < N; i++) {
            String s = br.readLine();

            for (int j = 0; j < M; j++) {
                char c = s.charAt(j);

                // 해당 값이 1일 경우 주변에서 여기로 올 수 있는 것이므로 주변에 간선으로 추가
                // (갈 수 있는 방향 추가 : 0 = 오른쪽 | 1 = 아래 | 2 = 위 | 3 = 왼쪽 )
                if(c == '1') {
                    if(j+1 < M) list[i][j+1].add(0);
                    if(i+1 < N) list[i+1][j].add(1);
                    if(i-1 >= 0) list[i-1][j].add(2);
                    if(j-1 >= 0) list[i][j-1].add(3);
                }
            }
        }

        // BFS 확인
        BFS(new Node(0,0));

        bw.write(count + "");
        // 출력
        bw.flush();
        bw.close();
    }

    public static void BFS(Node node) {
        // 시작 노드 추가
        Queue<Node> queue = new LinkedList();
        queue.add(node);
        isChecked[node.x][node.y] = true;

        // 다음 queue가 없을 때까지
        while (!queue.isEmpty()) {
            count++;

            // 이번 count 인접 노드 다 확인
            int queueSize = queue.size();
            for(int k = 0; k<queueSize; k++) {
                node = queue.poll();

                // 종료 노드에 도착했을 경우 끝내기
                if (node.x == N - 1 && node.y == M - 1) {
                    return;
                }

                // 인접 노드 확인
                for (int i = 0; i < list[node.x][node.y].size(); i++) {
                    int gotoWhere = list[node.x][node.y].get(i);

                    // 확인한 노드가 아니면 queue에 삽입 후 확인했음을 기록
                    switch (gotoWhere) {
                        case 0:
                            if (!isChecked[node.x][node.y - 1]) {
                                isChecked[node.x][node.y - 1] = true;
                                queue.add(new Node(node.x, node.y - 1));
                            }
                            break;
                        case 1:
                            if (!isChecked[node.x - 1][node.y]) {
                                isChecked[node.x - 1][node.y] = true;
                                queue.add(new Node(node.x - 1, node.y));
                            }
                            break;
                        case 2:
                            if (!isChecked[node.x + 1][node.y]) {
                                isChecked[node.x + 1][node.y] = true;
                                queue.add(new Node(node.x + 1, node.y));
                            }
                            break;
                        case 3:
                            if (!isChecked[node.x][node.y + 1]) {
                                isChecked[node.x][node.y + 1] = true;
                                queue.add(new Node(node.x, node.y + 1));
                            }
                            break;
                    }
                }
            }
        }
    }

    static class Node {
        public int x;
        public int y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}