[코딩테스트] 백준 2178 자바

백준 2178

백준 2178 문제

해당 문제의 n과 m의 최댓값은 100이고, 시간 제한은 1초이기에 어떠한 시간 복잡도의 알고리즘을 사용하여도 해결이 가능한 문제이다.

따라서, 그래프 완전 탐색 알고리즘 중 DFS나 BFS 둘 중 아무거나 사용해서 풀어도 된다.

하지만, depth의 이동에 따라 depth의 값을 관리해야 되는 DFS보다 depth를 차례대로 탐색하면서 도착 위치에 도착하였을 때의 depth값을 출력하면 되는 BFS가 좀 더 수월하여 BFS를 사용해보았다.

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

public class Boj2178 {

    static int[] dx = {0, 0, -1, 1}; // 상하좌우 x방향
    static int[] dy = {-1, 1, 0, 0}; // 상하좌우 y방향
    static boolean[][] visited; // 방문 기록을 담는 배열
    static int[][] maze; // 미로를 담는 배열
    static int n, m; // 미로의 세로, 가로 길이

    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()); // 미로의 가로 길이
        visited = new boolean[n][m]; // 방문 기록 배열 생성
        maze = new int[n][m]; // 미로 배열 생성

        // 입력값을 받아 미로 초기화
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for (int j = 0; j < m; j++) {
                maze[i][j] = Integer.parseInt(line.substring(j, j + 1));
            }
        }

        bfs(0, 0); // bfs 시작
        System.out.println(maze[n - 1][m - 1]); // 도착 위치의 값(최단 거리) 출력
    }

    private static void bfs(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j}); // 시작점 좌표를 큐에 저장
        visited[i][j] = true; // 시작점 좌표 방문 기록
        while (!queue.isEmpty()) { // 큐에 값이 없을 때까지 반복
            int[] now = queue.poll(); // 큐에 값을 꺼내서 현재 좌표에 저장
            for (int k = 0; k < 4; k++) { // 상하좌우 탐색
                int x = now[0] + dx[k]; // 현재 좌표에서 상하좌우의 x좌표
                int y = now[1] + dy[k]; // 현재 좌표에서 상하좌우의 y좌표
                if (x >= 0 && y >= 0 && x < n && y < m) { // 이동한 좌표가 미로의 범위를 넘어서면 안되고
                    if (maze[x][y] != 0 && !visited[x][y]) { // 0이여서 갈 수가 없거나 방문한 곳이면 안됨
                        visited[x][y] = true; // 이동 가능한 좌표를 방문 기록
                        maze[x][y] = maze[now[0]][now[1]] + 1; // 시작점에서 이동 가능한 좌표까지의 최대 거리를 저장
                        queue.offer(new int[]{x, y}); // 이동 가능한 좌표를 큐에 저장
                    }
                }
            }
        }
    }
}

풀이

1. 해당 미로는 상하좌우로 이동이 가능하기 때문에 상하좌우로 이동할 때의 x방향과 y방향을 dx와 dy로 생성한다.
2. 방문 기록을 담을 visited 2차원 배열을 선언한다.
3. 미로의 데이터를 담을 maze 2차원 배열을 선언한다.
4. 미로의 세로, 가로 길이를 담을 n, m 변수를 선언한다.
5. BufferedReader와 SringTokenizer로 입력된 문자열을 받아 n과 m을 초기화해준다.
6. n과 m 길이 만큼의 visited와 maze 2차원 배열을 생성한다.
7. StringTokenizer로 문자열을 입력 받고 substring() 메서드로 문자열을 나누어 maze 2차원 배열을 초기화한다.
8. 시작점 (0, 0)을 bfs() 메서드의 인자로 전달하여 BFS를 실행한다.
9. bfs() 메서드는 Queue를 생성하고, 시작점의 좌표를 정수형 배열로 받아 저장하고, visited 2차원 배열에 방문 기록한다.
10. while(!queue.isEmpty())를 통해 큐가 빌 때까지 무한 반복을 한다.
11. 큐에서 좌표를 꺼내서 현재 좌표를 가리키는 now 배열 변수에 저장한다.
12. dx와 dy를 사용하여 4번의 반복을 통해 현재 좌표에서 상하좌우로 이동할 때의 x좌표와 y좌표를 구한다.
13. 구해진 x좌표와 y좌표가 미로의 범위를 넘어서지 않고, 0이여서 갈 수가 없거나 방문한 곳이 아니라면 방문 배열에 기록한다.
14. 그리고 이동 가능한 좌표의 값에 현재 좌표의 값 +1를 통해 최단 거리를 기록한다.
15. 이동 가능한 좌표를 큐에 저장한다.
16. while(!queue.isEmpty())를 통해 반복을 하며 모든 이동 가능한 좌표로 이동하며 시작점에서 각 이동 가능한 좌표까지의 최단거리를 입력한다.
17. 반복문이 종료되고 도착 위치의 좌표값을 출력하면 시작점에서 도착 위치까지의 최단 거리를 알 수 있다.