BOJ(백준 온라인 저지) 2178번 with 자바[JAVA]

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

2178번: 미로 탐색

---

미로 탐색의 경우 BFS 를 사용해야 한다는 것은 아는데...

어떻게 구현해야 할지 몰랐습니다.

 

우선 Node 클래스를 만들었습니다.

 

그리고 미로에 해당하는 행렬을 입력받아 maze 변수에 넣어줍니다.

 

처음 시작하는 노드(* 0,0) 를 생성하고 그 노드에 인접 리스트에

(0,0)에 대해 상, 하, 좌, 우에 1이 있고 방문한 적이 없다면 노드를 추가해주는 방식을 사용했습니다.

(* 상, 하, 좌, 우로 움직였을 때 행렬의 index 를 넘어간다면 인접 리스트에 추가하지 않는 기능도 넣었습니다.)

그리고 이 기능을 재귀적으로 수행합니다.

 

public static void makeNode(Node startNode, ...)
{
	/* 시작 노드의 좌표를 받아옵니다.
    그 좌표에 대해 상, 하, 좌, 우에 해당하는 좌표를 받아줍니다.
    
    만약 4방향의 좌표들 중 행렬의 index 를 넘어가면 인접리스트에 추가하지 않습니다.
    만약 4방향의 좌표들 중 미로행렬의 값이 0 이거나 방문을 한 좌표이면 인접리스트에 추가하지 않습니다.
    
    모두 아니라면
    startNode.addNode(new Node()); // 상, 하, 좌. 우 노드 추가
    
    그리고 그 노드에 대해 다시 makeNode 함수를 수행합니다.
    makeNode(인접한 노드);
    
    이렇게 한다면 인접한 노드들끼리 재귀적으로 인접리스트를 형성하게됩니다.
    */
}

 

이렇게 하니 문제가 있었습니다.

 

• 첫 번째

이렇게 하니 노드의 인접 리스트를 만들어주는 행위 자체가 탐색이 됩니다. 만약 인접 리스트를 만들어주고 다시 시작 노드에서부터 BFS 를 수행한다면 또 다시 탐색하는 것이 되서 기능이 겹치게 됩니다. 

 

• 두 번째

이게 좀 큰데, 재귀적으로 수행하니 DFS 가 되었습니다.

DFS의 방식으로 인접리스트를 수행하니 빠지는 노드가 생깁니다.

입력이 이렇게 들어오는 경우를 생각해보겠습니다. 

4 6
110110
110110
111111
111101

 

이 경우 시작 노드는 미로 행렬의 (0,0) 위치입니다. 

시작 노드에 대해 상, 하, 좌, 우 이동할 수 있는지 확인합니다.

본 미로의 경우 오른쪽 방향과 아래 방향 모두 이동 가능합니다.

 

이때 문제가 발생합니다.

 

어떤 노드 먼저 인접리스트에 추가하고, 재귀를 실행할 것인가?

 

만약 상, 하, 좌, 우 의 순으로 인접리스트에 추가하고 재귀를 실행한다고 가정한다면,

인접리스트는

 

(0,0) -> (1,0) -> (2,0) -> (3,0) -> (3,1) -> (2,1) -> (1,1) -> (0,1) -> 이동불가 (2,1)로 이동

-> (2,2) -> (2,3) -> (1,3) -> (0,3) -> (0,4) -> (1,4) -> (2,4) -> 좌 방향(2,3) 은 방문한 적 있으니 우 방향 탐색

-> (2,5) -> (3,5) -> 목적지 도착 makeNode 함수 종료

 

좀 길지만 천천히 따라가면 makeNode 가 인접 리스트를 채우는 길을 볼 수 있습니다.

 

이때 인접리스트에 추가되지 않는 Node 가 생깁니다.

(3,2), (3,3), (3,4) 입니다.

이 노드들이 앞으로 BFS 탐색을 할 때 쓰이지 않는다면 상관 없지만 그렇지 않을 가능성이 더 높습니다.

 

또한 인접리스트를 탐색하는 과정이라 생각한다면

 

(0,0) -> (1,0) -> (2,0) -> (3,0) -> (3,1) -> (2,1) -> (1,1) -> (0,1) -> 이동불가 (2,1)로 이동 -> (2,2)

 

에서 볼 수 있듯이 끝까지 갔다가 이동 불가하니 마지막 분기점으로 돌아가 다시 탐색을 수행하는 것으로 볼 수 있습니다.

이는 DFS 에 해당하고 미로의 최소 경로를 따지는 문제와 맞지 않습니다.

 

 

이러한 이유들로 해당 함수는 적절하지 않습니다.

 

 

 

 

다시 생각해보면

미로 행렬 자체가 노드를 나타냅니다. 이걸 노드로 저장하고 다시 BFS 를 할 필요 없이

미로 행렬의 데이터를 가지고 BFS 를 수행하면 됩니다.

 

BFS 는 Queue 자료구조를 통해 구현 가능합니다.

Queue 에 시작 위치를 담고 BFS 를 시작합니다.

 

처음 Queue 에서 poll 하고 poll 한 위치 (* 시작 노드) 에 대해 상하좌우 이동 가능성을 검토합니다.

 

만약 상하좌우 위치가 index 를 넘어간다면 추가 기능을 수행하지 않고 넘어갑니다.

만약 상하좌우 위치가 방문한 적이 있거나 이동할 수 없는 곳이라면 (* 미로 행렬의 0 부분) 넘어갑니다.

 

그렇지 않은 경우 상하좌우 위치를 Queue 에 담고 visited 를 true로 바꿔준 후

 

상하좌우 위치에 현재위치의 값을 더해줍니다.

(* 현재위치의 값은 시작위치에서 현재위치까지 이동한 거리를 의미합니다.)

 

다시 Queue 에서 poll 한 위치에 대해 상하좌우 이동가능성을 검토한 후 이를 반복합니다.

 

이렇게 하면 노드를 따로 생성하지 않고

미로 행렬의 데이터만을 이용하여

BFS 를 수행할 수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static int[][] maze;
    public static int N;
    public static int M;
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0, -1};
    public static boolean[][] visited;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        maze = new int[N][M];

        for(int i=0; i<N; i++)
        {
            String s = br.readLine();
            for(int j=0; j<M; j++)
            {
                maze[i][j] = s.charAt(j) - '0';
            }
        }

        visited = new boolean[N][M];
        visited[0][0] = true;

        bfs(0,0);

        int result = maze[N-1][M-1];
        System.out.println(result);
    }

    private static void bfs(int startRow, int startCol)
    {
        Queue<int[]> queue = new LinkedList<>();
        int[] startPos = {startRow, startCol};
        queue.add(startPos);

        while(!queue.isEmpty())
        {
            int[] nowPos = queue.poll();
            int nowRow = nowPos[0];
            int nowCol = nowPos[1];

            for(int i=0; i<4; i++)
            {
                if((nowRow + dr[i] < 0) || (nowCol + dc[i] >= M) || (nowCol + dc[i] < 0) || (nowRow + dr[i] >= N))
                    continue;

                if(visited[nowRow + dr[i]][nowCol + dc[i]] || maze[nowRow + dr[i]][nowCol + dc[i]] == 0)
                    continue;

                int[] nextPos = {nowRow + dr[i], nowCol + dc[i]};
                visited[nextPos[0]][nextPos[1]] = true;
                maze[nextPos[0]][nextPos[1]] += maze[nowRow][nowCol];
                queue.add(nextPos);
            }
        }
    }
}

---

• 느낀 점

BFS 든 DFS 든 노드 클래스를 만들고 탐색을 수행할 필요가 없을 수 있다.

재귀적으로 함수를 수행하면 DFS 의 느낌을 받을 수 있다.

BFS 는 미로 탐색과 같이 최소 경로 문제에서 쓰일 수 있다.