자바 코딩테스트 강좌, 경로 찾기

이 글에서는 경로 찾기 알고리즘 문제를 해결하는 과정과 이를 자바로 구현하는 방법에 대해 자세히 설명하겠습니다. 이 과정은 코딩 테스트를 준비하는 데 유익할 것입니다.

문제 설명

주어진 2D 격자에서 시작 위치(S)에서 목표 위치(G)까지 이동하는 경로를 찾아야 합니다. 격자 내의 일부 칸은 장애물(X)로 막혀 있으며, 상하좌우로만 이동할 수 있습니다.
이 문제를 해결하기 위해 BFS(너비 우선 탐색) 알고리즘을 사용할 것입니다.

예제 입력

예제 출력

시작 위치(S)에서 목표 위치(G)까지의 최소 경로 길이는 7입니다.

문제 해결 전략

이 문제를 해결하기 위해 BFS 알고리즘을 사용할 것입니다. BFS는 그래프의 모든 노드를 수준별로 탐색합니다.
이 알고리즘을 사용하면 최단 경로를 빠르게 찾을 수 있습니다. 각 위치에서 가능한 다음 위치를 모두 탐색하면서 목표(G)에 도달하게 되면 BFS의 특성상 최단 경로를 알고리즘에서 보장합니다.

알고리즘 단계

입력 데이터를 2D 배열로 변환합니다.
시작 위치(S)와 목표 위치(G)를 찾습니다.
Q(큐)를 사용하여 BFS 탐색을 시작합니다.
현재 위치의 상하좌우를 방문 가능한지를 체크하고 큐에 추가합니다.
목표 위치(G)에 도달하면 경로의 길이를 기록합니 다.
BFS가 종료되면 최단 경로를 반환합니다.

자바 코드 구현

이제 위의 알고리즘을 자바로 구현해 보겠습니다.

                import java.util.LinkedList;
                import java.util.Queue;

                public class PathFinding {
                    static class Position {
                        int x, y, distance;

                        Position(int x, int y, int distance) {
                            this.x = x;
                            this.y = y;
                            this.distance = distance;
                        }
                    }

                    static final int[] dx = {-1, 1, 0, 0};
                    static final int[] dy = {0, 0, -1, 1};

                    public static int bfs(char[][] grid, int startX, int startY) {
                        Queue queue = new LinkedList<>();
                        boolean[][] visited = new boolean[grid.length][grid[0].length];

                        queue.offer(new Position(startX, startY, 0));
                        visited[startX][startY] = true;

                        while (!queue.isEmpty()) {
                            Position current = queue.poll();

                            if (grid[current.x][current.y] == 'G') {
                                return current.distance;
                            }

                            for (int i = 0; i < 4; i++) {
                                int newX = current.x + dx[i];
                                int newY = current.y + dy[i];

                                if (isValid(grid, newX, newY, visited)) {
                                    visited[newX][newY] = true;
                                    queue.offer(new Position(newX, newY, current.distance + 1));
                                }
                            }
                        }

                        return -1; // Path not found
                    }

                    private static boolean isValid(char[][] grid, int x, int y, boolean[][] visited) {
                        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length &&
                               grid[x][y] != 'X' && !visited[x][y];
                    }

                    public static void main(String[] args) {
                        char[][] grid = {
                            {'S', '.', '.', 'X', 'G'},
                            {'.', 'X', '.', 'X', '.'},
                            {'.', 'X', '.', '.', '.'},
                            {'.', '.', '.', 'X', '.'},
                            {'.', 'X', '.', '.', 'E'}
                        };

                        int startX = 0, startY = 0; // S 위치
                        int result = bfs(grid, startX, startY);

                        if (result != -1) {
                            System.out.println("목표까지의 최소 경로 길이: " + result);
                        } else {
                            System.out.println("목표에 도달할 수 없습니다.");
                        }
                    }
                }

이 코드는 주어진 격자 내에서 시작 위치(S)에서 목표(G)까지의 최단 경로를 찾기 위해 BFS를 구현한 것입니다. 경로가 발견되면 최소 경로 길이를 출력합니다.

결론

이번 글에서는 자바를 이용하여 경로 찾기 알고리즘 문제를 해결하는 방법에 대해 설명했습니다. BFS를 통한 문제 해결은 최단 경로를 찾는 데 유리하며, 다양한 코딩 테스트에서 자주 출제되는 주제입니다.
알고리즘 문제 해결 경험을 통해 코딩 테스트에 대한 준비를 더욱 철저히 할 수 있습니다. 이러한 문제를 더 많이 연습하여 실력을 쌓아보세요!