https://school.programmers.co.kr/learn/courses/30/lessons/1844
DFS
public class Solution {
// 4방향으로 이동할 때 사용되는 상대 좌표 값
int[] x_list={0,0,1,-1};
int[] y_list={1,-1,0,0};
// 미로 맵에서 각 위치를 방문했는지 여부를 기록하는 배열
int[][] visited;
// 최단 경로의 길이를 저장하는 변수 (초기값: -1)
int min_cnt = -1;
public int solution(int[][] maps) {
// visited 배열 초기화 (미로 맵의 크기와 동일한 크기로 초기화)
visited = new int[maps.length][maps[0].length];
// DFS 메서드 호출 (출발점: (0, 0), 현재 경로의 길이: 1)
dfs(0, 0, maps, visited, 1);
// 최단 경로의 길이 반환
return min_cnt;
}
public int dfs(int x, int y, int[][] maps, int[][] visited, int cnt) {
// 미로 맵의 높이와 너비
int height = maps.length;
int width = maps[0].length;
// 현재 위치가 도착점인 경우
if (x == height - 1 && y == width - 1) {
// 최단 경로의 길이가 아직 저장되지 않았다면, 현재 경로의 길이를 저장
if (min_cnt == -1) {
min_cnt = cnt;
return 0;
}
// 이미 최단 경로의 길이가 저장되어 있고, 현재 경로의 길이가 더 작다면 업데이트
else if (min_cnt > cnt) {
min_cnt = cnt;
return 0;
}
}
// 다음 위치의 좌표를 저장할 임시 변수
int tempx = x;
int tempy = y;
// 4방향으로 탐색
for (int i = 0; i < 4; i++) {
// 다음 위치의 좌표 계산
tempx = x + x_list[i];
tempy = y + y_list[i];
// 다음 위치의 좌표가 미로 맵의 범위 내에 있는 경우
if ((tempx >= 0 && tempx < height) && (tempy >= 0 && tempy < width)) {
// 다음 위치가 길(값이 1)이고, 아직 방문하지 않은 곳이라면
if (maps[tempx][tempy] == 1 && visited[tempx][tempy] == 0) {
// 방문 표시
visited[tempx][tempy] = 1;
// 다음 위치로 재귀 호출 (경로의 길이 1 증가)
dfs(tempx, tempy, maps, visited, cnt + 1);
// 탐색 완료 후 방문 표시 제거
visited[tempx][tempy] = 0;
}
}
}
// 최단 경로의 길이 반환
return min_cnt;
}
}-
solution 메서드에서 visited 배열을 미로 맵의 크기와 동일한 크기로 초기화한다. 이 배열은 각 위치를 방문했는지 여부를 기록하는 데 사용된다.
-
dfs 메서드를 호출하여 출발점 (0, 0)에서 시작한다. 현재 경로의 길이인 cnt는 1로 초기화된다.
-
dfs 메서드에서는 먼저 현재 위치가 도착점인지 확인한다. 도착점이라면, 현재 경로의 길이를 min_cnt에 저장하거나 업데이트한다. min_cnt는 최단 경로의 길이를 저장하는 변수다.
-
현재 위치가 도착점이 아니라면, 4방향(오른쪽, 왼쪽, 아래, 위)으로 탐색을 진행한다.
-
먼저, 각 방향으로의 다음 위치 좌표를 계산합니다. 이때 x_list와 y_list에 저장된 상대 좌표 값을 사용한다.
-
계산된 다음 위치의 좌표가 미로 맵의 범위 내에 있는지 확인한다. 범위 내에 있다면, 해당 위치가 길(값이 1)이고, 아직 방문하지 않은 곳인지 확인한다.
-
다음 위치가 길이고, 방문하지 않은 곳이라면 다음과 같은 작업을 수행한다:
- visited 배열에 방문 표시를 한다.
- 해당 위치로 재귀 호출을 하여 dfs 메서드를 실행한다. 이때 cnt는 1 증가된 값으로 전달된다.
- dfs 메서드에서 반환된 값(최단 경로의 길이)이 min_cnt보다 작다면 min_cnt를 업데이트한다.
- 탐색 완료 후 visited 배열에서 방문 표시를 제거한다.
-
4방향 탐색이 완료되면, min_cnt를 반환한다.
-
solution 메서드에서 dfs 메서드에서 반환된 값인 min_cnt를 최종 결과로 반환한다.
배운 점
-
이 코드에서는 두갈래 길에서 오른쪽을 먼저 탐색한 후, 다시 두갈래 길로 돌아와서 안가본 길인 위쪽으로 가는 방식을 사용한다.
-
return 0의 의미
DFS 탐색에서 현재 위치가 도착점인 경우, 더 이상 탐색할 필요가 없기 때문에 현재 재귀 호출을 종료하고 상위 호출로 되돌아간다. return 0은 단순히 현재 재귀 호출에서 반환값이 필요하기 때문에 0을 반환하는 것이다. 실제로는 반환값이 사용되지 않는다. -
visited[tempx][tempy] = 0를 하는 이유
DFS 탐색 과정에서 visited 배열은 각 위치를 방문했는지 여부를 기록하는 데 사용된다.
특정 위치를 방문하면 visited 배열에 1을 표시하고, 그 위치에서 탐색을 완료한 후에는 다시 0으로 바꾼다. 이렇게 하는 이유는 나중에 다른 경로에서 해당 위치를 다시 방문할 수 있기 때문이다.
예를 들어, 두 갈래 길에서 한 방향으로 탐색을 완료한 후, 다시 두 갈래 길로 돌아와서 다른 방향을 탐색할 때 이전에 방문했던 위치를 다시 방문해야 한다. 이때 visited 배열에 1이 표시되어 있다면, 해당 위치를 건너뛰게 되므로 모든 경로를 제대로 탐색할 수 없다.
따라서 visited[tempx][tempy] = 1로 방문 표시를 한 후, 해당 위치에서의 탐색을 완료하면 visited[tempx][tempy] = 0으로 다시 0으로 바꾼다. 이렇게 하면 나중에 다른 경로에서 해당 위치를 다시 방문할 수 있게 된다.
이 방식은 백트래킹(backtracking) 알고리즘에서 자주 사용되는 기법이다. 현재 경로에서 특정 위치를 방문했다고 해서 다른 경로에서도 그 위치를 절대 방문하지 않는 것은 아니기 때문에, 탐색 완료 후에는 visited 배열의 값을 0으로 되돌려 놓아야한다.
BFS
import java.util.*;
class Position {
int x;
int y;
int cnt; // 시작점부터 현재 위치까지의 거리
public Position(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
}
class Solution {
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
public int solution(int[][] maps) {
return bfs(0, 0, maps);
}
public int bfs(int x, int y, int[][] maps) {
int n = maps.length;
int m = maps[0].length;
boolean[][] visited = new boolean[n][m];
Queue<Position> queue = new LinkedList<>();
// 시작 위치를 큐에 추가하고 방문 처리
queue.add(new Position(x, y, 1));
visited[x][y] = true;
while (!queue.isEmpty()) {
Position current = queue.poll();
// 도착지점에 도달한 경우 현재 경로의 길이 반환
if (current.x == n - 1 && current.y == m - 1) {
return current.cnt;
}
// 이동 시도
for (int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
// if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1 && !visited[nx][ny]) {
// nx와 ny가 지도의 범위 안에 있는지 확인
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
// 해당 위치가 방문하지 않은 길(1)인지 확인
if (maps[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true; // 방문 처리
queue.add(new Position(nx, ny, current.cnt + 1)); // 큐에 추가
}
}
}
}
// 도착지점에 도달하지 못한 경우
return -1;
}
}배운점
- 2차원 배열의 가로 길이는 maps[0].length로 표현할 수 있다.
만약 2차원 배열이
int[][] maps = {
{1, 1, 1, 0},
{0, 1, 1, 1},
{0, 0, 1, 1}
};
라면 maps[0]은 {1,1,1,0}이고, 이것의 길이는 4이기 때문에 이는 가로 길이가 되는 것이다.
-
x, y, 현재까지의 거리를 별도의 클래스로 만들어서 관리하는 방법도 있다.
-
queue.poll()로 요소를 current로 선택하여 이동을 시도한다.
