[백준] 2178: 미로 탐색 - Java (그래프 이론)

 

  목 차

• 문제
• 접근 방식
• 이 문제를 구현하며 알게된 것
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

이번에는 BFS 알고리즘으로 해당 문제를 해결하려고 한다. BFS는 가장 먼저 도착하는 것을 반환하면 되기 때문에 생각보다 간단하다. 

 

자바에는 컬렉션에 Queue 자료구조가 있어 그 것을 활용하면 된다. 

근데 LinkedList 의 Queue 는 객체로 되어있어 메모리를 상당히 잡아먹는다. 

 

그래서 나는 배열 형태의 Queue 자료구조를 만들기로 했다. 근데 javascript 와는 달리 Java 의 배열은 정적 배열이기에 Javascript 의 .push 같은 배열 메서드가 제공되지 않는다.

 

그래서 원형 큐(Circular Queue)를 알게되었고, 대안으로 선택하게 되었다. 원형 큐는 다음 소제목 '이 문제를 구현하며 알게된 것' 에서 언급하겠다.

 

 

이 문제는 weight 값만 추가하여 [N][M]에 도착했을 때의 weight 값을 출력하며 된다.

 

 

 

  이 문제를 구현하며 알게된 것

 

 

  원형 큐(Circular Queue)

 

front 와 end 포인터가 있을 때, end를 ++ 할 때 queue.length 와 같다면 end 를 0 으로 만든다.

front 역시 ++ 했을 때 queue.length 와 같다면 front 역시 0 으로 만든다.

 

 

 

  풀이

 

 

package src.graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class maze {

    public static void main(String[] args) throws Exception {


        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int[][] graph = new int[N + 2][M + 2];

        // 입력 배열화
        for(int i = 1; i <= N; i++){
            String mazeTokens = br.readLine();

            for(int j = 0; j < M; j++){
                graph[i][j+1] = mazeTokens.charAt(j) - '0';

            }
        }

        int[] first = {1, 1, 1};


        // Main
        // Queue 자료구조 - for BFS
        Queue queue = new Queue(100);


        queue.enqueue(first);
        while(!queue.isEmpty()){

            int[] data = queue.dequeue();
            int x = data[1];
            int y = data[0];
            int w = data[2];

            if(x == M && y == N) {
                System.out.println(w);
                break;
            }

            graph[y][x] = 0;

            // 상
            if(graph[y - 1][x] != 0){
                int[] point = {y - 1,x , w + 1};
                graph[y - 1][x] = 0;
                queue.enqueue(point);
            }
            // 하
            if(graph[y + 1][x] != 0){
                int[] point = {y + 1,x , w + 1};
                graph[y + 1][x] = 0;
                queue.enqueue(point);
            }
            // 우
            if(graph[y][x + 1] != 0){
                int[] point = {y, x + 1 , w + 1};
                graph[y][x + 1] = 0;
                queue.enqueue(point);
            }
            // 좌
            if(graph[y][x - 1] != 0){
                int[] point = {y,x - 1, w + 1};
                graph[y][x - 1] = 0;
                queue.enqueue(point);
            }


            }


        }
    public static class Queue {
        private int[][] queue;
        private int front;
        private int end;
        private int capacity;

        public Queue(int size){
            queue = new int[size][3];
            front = 0;
            end = 0;
            capacity = size;
        }

        public void enqueue(int[] el){
            // 추가사항: 용량이 꽉 차면 에러 발생

            queue[end] = el;

            end++;

            if(end == capacity) end = 0;
        }

        public int[] dequeue(){
            // 추가사항: 비어있다면 에러 발생
            int[] data = queue[front];
            front++;
            if(front == capacity) front = 0;

            return data;
        }

        public boolean isEmpty(){
            return front == end;
        }

        public boolean isFull(){
            if(((end + 1 == capacity) && front == 0) || (end + 1 == front)) {
                return true;
            } else {
                return false;
            }
        }

    }


    }