문제 소개
BFS 풀이
직관적으로 보았을 때, 현재 셀을 기준으로 상하좌우로 이동하며 가능한 경로를 탐색하기 때문에 DFS나 BFS로 해결가능한 문제이다. 방문 조건 중 하나로 1인 칸으로만 이동이 가능하므로 1인 칸을 그래프에서의 하나의 노드로 볼 수 있기 때문이다. 다만 DFS로 풀었을 경우, 재귀적인 특성으로 인해 depth를 다루기가 까다롭다. 때문에 depth 대로 쭉 내려오는 것이 가능한 BFS를 사용하는 것이 더 간단한 풀이가 될 것으로 보인다. BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 바로 다음 깊이로 내려가는 식으로 동작하기 때문이다.
첫번째 출력 예시를 통해 예상되는 실행 결과를 확인해보았다. 시작점으로부터 출발하여 방문 가능한 셀들을 한 칸 씩 이동할때마다 1씩 증가시키고, 마지막 끝 점에 도달하면 최소 이동 칸 수를 반환한다.
주어진 테스트케이스를 만족하여 아래의 코드로 제출하였으나 시간초과 에러가 발생했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[][] arr;
static boolean[][] visited;
public static void bfs(int row, int col) {
int n = arr.length;;
int m = arr[0].length;
System.out.println(Arrays.toString(arr[0]));
// 시작점 방문표시
visited[row][col] = true;
// 상하좌우
int [][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
// Queue 선언
Queue<int []> queue = new ArrayDeque<>();
// 시작 지점 (x, y) 큐에 삽입
queue.offer(new int[] {row, col});
// 큐 빌때까지 실행
while (!queue.isEmpty()) {
int[] current = queue.poll();
// row
int x = current[0];
// col
int y = current[1];
// 상하좌우 이동
for (int[] dir: dirs) {
// 상하좌우로 이동한 row, col의 좌표
int dx = x + dir[0];
int dy = y + dir[1];
// 방문 조건
// 인덱스가 배열을 넘어가면 안됨
if (dx >= 0 && dx < n && dy >= 0 && dy < m) {
// 방문 가능 조건: 칸의 숫자가 0이 아니어야 하고 아직 방문하지 않은 상태
if (arr[dx][dy] != 0 && !visited[dx][dy]) {
visited[x][y] = true;
// depth 값을 갱신해줌
arr[dx][dy] = arr[current[0]][current[1]] + 1;
// 새로운 x,y를 만들어 큐에 삽입
queue.add(new int[] {dx, dy});
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
arr = new int [n][m];
visited = new boolean[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++) {
arr[i][j] = Integer.parseInt(line.substring(j, j+1));
}
}
bfs(0, 0);
// 인덱스가 0부터 시작하니 마지막 칸의 좌표값에 -1을 해줘야함.
System.out.println(arr[n-1][m-1]);
}
}
메모리 초과 문제 해결
위의 시간초과 문제를 해결하기 위해서 bfs 함수에 리턴값을 반환하도록 하고, 큐에 현재 셀까지의 이동 횟수를 추가적으로 삽입하도록 하였다. 그리고 큐에 담긴 x, y 좌표의 값이 미로의 마지막 종점 좌표와 같다면 큐에서 받아온 최소 이동 횟수를 출력할 수 있도록 수정하였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[][] arr;
static boolean[][] visited;
public static int bfs(int row, int col) {
int n = arr.length;
int m = arr[0].length;
// 시작점 방문표시
visited[row][col] = true;
// 상하좌우
int [][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
// Queue 선언
Queue<int []> queue = new ArrayDeque<>();
// 시작 지점 (x, y) 큐에 삽입
queue.offer(new int[] {row, col, arr[row][col]});
// 큐 빌때까지 실행
while (!queue.isEmpty()) {
int[] current = queue.poll();
// row
int x = current[0];
// col
int y = current[1];
int count = current[2];
if (x == n-1 && y == m-1) {
// 최단 경로 반환
return count;
}
// 상하좌우 이동
for (int[] dir: dirs) {
// 상하좌우로 이동한 row, col의 좌표
int dx = x + dir[0];
int dy = y + dir[1];
// 방문 조건
// 인덱스가 배열을 넘어가면 안됨
if (dx >= 0 && dx < n && dy >= 0 && dy < m) {
// 방문 가능 조건: 칸의 숫자가 0이 아니어야 하고 아직 방문하지 않은 상태
if (arr[dx][dy] != 0 && !visited[dx][dy]) {
visited[dx][dy] = true;
// depth 값을 갱신해줌
arr[dx][dy] = arr[current[0]][current[1]] + 1;
count = arr[dx][dy];
// 새로운 x,y를 만들어 큐에 삽입
queue.add(new int[] {dx, dy, count});
}
}
}
}
// 도착하지 못한 경우
return 0;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
arr = new int [n][m];
visited = new boolean[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++) {
arr[i][j] = Integer.parseInt(line.substring(j, j+1));
}
}
System.out.println(bfs(0, 0));
}
}
위의 두 코드는 큰 차이가 없어 보이지만 첫 번째 코드는 최소 이동 횟수를 저장하기 위해 "arr" 배열을 사용하고 있다. arr[n-1][m-1]을 출력하여 최소 이동 횟수 결과를 내보내지만, 배열의 모든 좌표에 최소 이동 횟수를 저장하는 방식으로 작동하므로 입력 데이터 크기에 따라 메모리 사용량이 증가할 수 있다. 반면에 두 번째 코드에서는 결과를 내보내는데에 "arr" 배열을 사용하는 대신 최소 이동 횟수를 bfs 함수 내에서 직접적으로 반환하는 방식이므로 메모리 사용량이 상대적으로 적을 수 있다.
'Algorithm > Java' 카테고리의 다른 글
[BOJ] 2751. 수 정렬하기2 (0) | 2024.09.12 |
---|---|
[BOJ] 2606. 바이러스 (0) | 2024.08.08 |
[BOJ] 1260. DFS와 BFS (0) | 2024.04.11 |
[BOJ] 2644. 촌수계산 (1) | 2024.03.05 |
[BOJ] 13305. 주유소 (0) | 2024.01.18 |