https://school.programmers.co.kr/learn/courses/30/lessons/1844
풀이
이 문제는 미로 탐색과 유사한 문제로, 최단 경로를 찾는 문제입니다. 미로에서 최단 경로를 찾기 위해서는 BFS(너비 우선 탐색) 알고리즘을 사용하는 것이 적합합니다. BFS는 가까운 노드부터 탐색을 진행하기 때문에, 최단 경로 문제를 해결하는 데 매우 효율적입니다.
해결 전략
- BFS 알고리즘 사용:
- BFS는 시작점에서부터 단계별로 탐색을 진행하기 때문에, 최단 거리를 구할 때 적합합니다.
- BFS는 큐(Queue)를 사용하여 현재 노드와 연결된 모든 노드를 탐색합니다.
- 맵 탐색:
- 상, 하, 좌, 우 네 방향으로 움직일 수 있기 때문에, 각 방향에 대해 가능한지 확인하면서 이동합니다.
- 벽이 있는 곳(
maps[x][y] == 0)은 이동할 수 없고, 벽이 없는 곳(maps[x][y] == 1)으로만 이동할 수 있습니다.
- 경계 조건:
- 맵을 벗어나지 않도록 경계 조건을 설정합니다.
- 상대 팀 진영에 도달할 수 없는 경우에는 -1을 반환해야 합니다.
import java.util.*;
class Solution {
// 상, 하, 좌, 우 네 방향 탐색을 위한 배열
static int[] dx = {-1, 1, 0, 0}; // 상하
static int[] dy = {0, 0, -1, 1}; // 좌우
public int solution(int[][] maps) {
int n = maps.length; // 행의 크기
int m = maps[0].length; // 열의 크기
// BFS를 이용해 최단 경로 탐색
return bfs(maps, n, m);
}
public int bfs(int[][] maps, int n, int m) {
// 큐를 이용해 BFS 구현, (x, y, 거리)를 저장
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0, 1}); // 시작점 (0, 0)에서 시작, 거리 1
// 방문 여부 체크 배열
boolean[][] visited = new boolean[n][m];
visited[0][0] = true;
// BFS 탐색 시작
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
int dist = current[2];
// 상대 팀 진영에 도착한 경우
if (x == n - 1 && y == m - 1) {
return dist; // 최단 거리 반환
}
// 상, 하, 좌, 우로 이동
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 맵을 벗어나지 않고, 방문하지 않았으며, 벽이 아닌 경우
if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny] && maps[nx][ny] == 1) {
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny, dist + 1}); // 이동 후 거리 +1
}
}
}
// 상대 팀 진영에 도착할 수 없는 경우
return -1;
}
}
코드 설명
- BFS 탐색 준비:
dx[]와dy[]배열은 상하좌우 네 방향으로의 이동을 표현합니다.bfs()함수에서 큐(Queue)를 사용해 BFS 탐색을 진행합니다.- 시작 위치
(0, 0)에서 시작하며, 초기 거리는 1로 설정합니다.
- BFS 구현:
queue.offer(new int[]{0, 0, 1}): 큐에 시작 위치(0, 0)과 초기 거리 1을 넣습니다.- 큐에서
poll()로 값을 꺼내, 현재 위치(x, y)와 거리를 확인합니다. - 만약 상대 팀 진영
(n-1, m-1)에 도착하면, 현재까지의 이동 거리를 반환합니다. - 상하좌우 네 방향으로 이동할 수 있는지 확인한 뒤, 갈 수 있는 곳이면 큐에 새로운 위치와 거리를 넣습니다.
- 방문한 위치는 다시 방문하지 않도록
visited배열로 관리합니다.
- 최종 결과:
- 상대 팀 진영에 도착하면 그때까지의 이동 거리를 반환합니다.
- 도착하지 못하고 큐가 비면 도달할 수 없는 경우이므로
1을 반환합니다.
시간 복잡도
- BFS 탐색은 각 노드를 한 번씩 방문하며, 각 노드는 최대 네 방향(상하좌우)으로 이동 가능성을 체크합니다.
n은 맵의 행 크기,m은 열 크기이므로 맵의 모든 칸을 방문할 때의 시간 복잡도는 O(n * m)입니다.
공간 복잡도
- 큐는 BFS 과정에서 최대
n * m개의 좌표를 저장할 수 있습니다. 또한 방문 여부를 체크하는visited배열도 크기가n * m입니다. - 따라서 공간 복잡도는 O(n * m)입니다.
사용된 알고리즘 및 자료구조
- BFS (너비 우선 탐색):
- BFS는 시작점에서부터 목표 지점까지 최단 경로를 찾는 데 적합한 알고리즘입니다. 탐색을 한 단계씩 진행하며 가장 가까운 위치부터 탐색하므로 최단 경로 문제에 사용됩니다.
- 큐(Queue):
- BFS 탐색에서 사용됩니다. 현재 위치와 거리를 함께 저장하여 탐색을 진행합니다.
- 2차원 배열:
- 게임 맵을 표현하는 데 사용되며, 각 칸의 상태(벽, 길)를 나타냅니다.
visited배열은 각 위치의 방문 여부를 저장하여 중복 방문을 방지합니다.
결론
이 문제는 BFS 알고리즘을 사용하여 최단 경로를 찾는 문제입니다. BFS는 최단 거리를 찾는 데 매우 적합한 알고리즘이며, 큐를 사용하여 구현합니다. 시간 복잡도는 O(n * m)로, 입력 크기가 최대 100 x 100일 때도 효율적으로 동작할 수 있습니다.
