문제
https://www.acmicpc.net/problem/4485
풀이
이차원 배열에서 (0, 0)부터 출발하여 (N-1, N-1)에 도착할 때, 지나온 좌표에 쓰여진 값들의 합이 최소가 되도록 만드는 문제이다. 이 문제는 완전 탐색과 DP를 합친 다익스트라 알고리즘을 이용하여 푸는 문제이다.
먼저 문제를 러프하게 풀어보자.
(0, 0)와 인접한 좌표는 (0, 1)과 (1, 0)이다. 두 좌표의 값은 각각 5, 3이므로 값이 더 작은 3을 선택
(1, 0)와 인접한 좌표는 (1, 1)과 (2, 0)이다. (0, 0)은 지나온 자리므로 고려하지 않는다. 두 좌표의 값은 각각 9, 3이므로 3을 선택
...
이런 식으로 (N-1, N-1)까지 구하기
하지만 매번 인접한 좌표들의 값만을 비교해서 경로를 선택하는 것은 실수다. 당장에는 더 작은 수를 골랐을지 몰라도, 더 먼 길로 돌아가가게 되어 작은 수들이 무수히 많이 더해질 수도 있다. 오히려 값은 크지만 도착지와 가까운 경로로 가는 것이 더 효율적일지도 모른다. 따라서 인접 좌표를 방문했을 때 누적값을 비교해서 경로를 정해야 한다.
그리고 매번 최소값인 좌표를 찾아서 그 경우만 탐색하는 것도 옳지 않은 방법이다. 모든 경우의 수를 다 고려해야 하므로 완전 탐색(bfs)을 이용할 것이다. dfs가 아닌 bfs를 쓰는 이유는 최적 경로 문제는 bfs가 답을 찾는 데 더 적은 시간이 걸려 유리하기 때문이다. bfs는 큐에 좌표를 넣은 후 그 좌표를 꺼내 인접 좌표를 구하는 동작을 반복할 것이다.
인접 좌표를 방문할 때마다 누적 비용을 계산할 것인데, 이 동작이 반복되면서 앞에서 구한 누적 비용을 재사용해야 하므로 최소값을 저장하는 이차원 배열 dp를 따로 마련해두자. dp의 초기값은 모 Integer.MAX_VALUE로 설정되어있다. dp에 저장되어있는 값보다 더 작은 비용이 계산되면 그 값으로 변경해야 하기 때문에 애초에 정수의 최댓값으로 설정해두었다. dp에 현재 저장된 값보다 이전 좌표 누적 값 + 현재 좌표 값이 더 크면 해당 값으로 갱신한다.
이 동작을 N*N번 반복하면 dp에 값이 모두 채워졌을 것이다. 최종적으로 dp[N-1][N-1]을 출력하면 된다.
코드1
import java.io.*;
import java.util.*;
public class Main{
static boolean[][] check;
static int[][] arr;
static int[][] dp;
static Queue<Coordinate> q = new LinkedList<>();
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
//N를 입력받고 N*N 배열을 입력받는다. 0을 입력받으면 그만 입력받고 출력
int N = -1;
int probNum = 0;
while(true){
probNum++;
N = Integer.parseInt(br.readLine());
if(N == 0) break;
check = new boolean[N][N]; //방문체크
arr = new int[N][N]; //입력받은 배열
dp = new int[N][N]; //계산된 최소 비용을 저장할 배열
for(int i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++){
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
dp[i][j] = Integer.MAX_VALUE;
}
}
dp[0][0] = arr[0][0];
bfs(N, 0,0);
bw.write("Problem " + probNum + ": " + dp[N-1][N-1] + "\n");
}
bw.close();
}
static void bfs(int N, int x, int y){
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
q.add(new Coordinate(x, y));
check[x][y] = true;
while(!q.isEmpty()){
Coordinate c = q.poll();
//c의 인접 좌표 선정
for(int i=0; i<4; i++){
int newX = c.x + dx[i];
int newY = c.y + dy[i];
//배열 범위를 넘은 좌표 제외
if(newX<0 || newX>=N || newY<0 || newY>=N)
continue;
//이미 방문해서 dp값이 저장되어있는 경우, 그 값이 새로 구한 값보다 작으면 dp값 갱신하지 않고 넘어감
if(check[newX][newY] && dp[newX][newY] <= dp[c.x][c.y] + arr[newX][newY])
continue;
//인접한 좌표들의 최소비용을 구해서 dp에 저장함
dp[newX][newY] = dp[c.x][c.y] + arr[newX][newY];
//구한 인접 좌표를 큐에 삽입
q.add(new Coordinate(newX, newY));
check[newX][newY] = true;
}
}
}
}
class Coordinate{
int x, y;
Coordinate(int x, int y){
this.x = x;
this.y = y;
}
}코드2
import java.util.*;
public class boj_4485 {
static Scanner scanner = new Scanner(System.in);
static Queue<Point> q = new LinkedList<>();
public static void main(String[] args){
StringBuffer sb = new StringBuffer();
int probCount = 0;
while(true){
int N = scanner.nextInt();
if(N == 0)
break;
probCount++;
sb.append("Problem " + probCount + ": " + bfs(input(N)) + "\n");
}
System.out.print(sb);
}
static int[][] input(int N){
//값을 입력받아 이차원 배열을 생성하는 함수
int[][] arr = new int[N][N];
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
arr[i][j] = scanner.nextInt();
}
}
return arr;
}
static int bfs(int[][] arr){
int N = arr.length;
int[][] arr2 = new int[N][N];
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
arr2[i][j] = N*N*9;
}
}
arr2[0][0] = arr[0][0];
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
q.offer(new Point(0, 0));
while(!q.isEmpty()){
Point now = q.poll();
for(int i=0; i<4; i++){
int newX = now.x + dx[i];
int newY = now.y + dy[i];
//배열 범위를 넘는 좌표 제외
if(newX < 0 || newX >= N || newY < 0 || newY >= N)
continue;
if(arr2[newX][newY] > arr2[now.x][now.y] + arr[newX][newY]){
arr2[newX][newY] = arr2[now.x][now.y] + arr[newX][newY];
q.offer(new Point(newX, newY));
}
}
}
return arr2[N-1][N-1];
}
}
class Point{
int x, y;
Point(int x, int y){
this.x = x;
this.y = y;
}
}Note
- 처음 풀어본 다익스트라 문제인데, 완탐과 dp에 대해서 잘 공부가 되어있으니까 아이디어 떠올리는 것은 어렵지 않았다.
- 다만 bfs 구현 시 큐가 쓰이는 것, 방문 체크는 큐 삽입 시 해야 데이터가 중복으로 들어가지 않는다는 점을 잊지 말자.
- bfs 함수에서 이미 방문한 좌표에 대한 최솟값을 처리하는 부분에서 조금 시간이 걸렸다. 일반적인 최적경로 찾는 bfs를 구현할 때는 이미 방문한 노드를 다시 한 번 방문하지 않고 그냥 지나갔는데, 이번에는 다시 방문하게 되면 다른 경우의 값이 생성되어 원래 저장되어있는 값과 비교해야 하므로 그 부분을 반영했다.
★ 6/13 다시 풀며 틀린 부분
최솟값을 업데이트하기 위해 이미 방문한 포인트를 또 방문해야 한다는 생각에, bfs()에 방문 체크 자체를 없앴다.
그런데 ide에서 메모리 초과가 발생했다. 중복된 포인트가 큐에 계속해서 삽입되어 생긴 문제인 것 같았다.
그래서 코드1과 같이 방문 체크를 포함하여 다시 수정했는데, ide에서는 테케가 정상 출력되었다.
하지만 백준에서 메모리 초과가 발생했다.
코드를 몇 번이고 확인해봤는데 모든 부분에서 문제가 없는 것 같아 백준에서 메모리 초과가 발생하는 이유를 구글링했다.
10,000,000개의 배열을 사용해서 메모리 초과가 생긴 것이냐는 질문이 있었다.
답변은 천만 개라고 해도 int형이면 40MB정도라서 초과가 나지 않을 것이고, 코드에서 원인을 찾으라고 했다.
내가 오늘 새로 짠 코드의 로직은 한 달 전에 맞힌 코드와 같지만, N을 입력받을 때마다 새로운 배열을 생성한다는 점만 다르다. 그럼 진짜 너무 많은 배열을 생성해서 생긴 문제일까?
문제 조건에서는 메모리 제한이 256MB = 256*10^6 byte인데, 2<=N<=125 이므로 최악의 경우 125*125 크기의 이차원 배열이 계속해서 생성된다. 생성 횟수는 조건에 없다. 0이 입력될 때까지 이차원 배열이 계속 생성된다.
그래서 배열을 다 썼으면 GC에 의해 자동으로 삭제되도록 arr = null, arr2 = null을 추가해봤지만 실패
arr, arr2를 전역으로 선언해서 재사용해봤지만 이것도 실패
그러면 배열을 너무 많이 생성해서 생긴 문제는 아니라는 것..
마지막으로 챗지피티한테 물어보니 중복된 포인트가 큐에 삽입되어 메모리 초과가 났다고 한다.
그럼 처음 생각했던 문제가 맞다는 것이다.
분명히 방문 체크를 추가해서 해결했다고 생각했는데 여전히 문제였나보다.
bfs의 while문을 위에서 아래로 코드를 바꿨더니 통과되었다.
//이미 방문하여 dp값이 저장되어있는 경우, 그 값이 새로운 값보다 작으면 dp 갱신하지 않고 넘어감
if(check[newX][newY] && arr2[newX][newY] < arr2[now.x][now.y] + arr[newX][newY])
continue;
//인접한 좌표의 최소비용을 구해 dp에 저장
arr2[newX][newY] = arr2[now.x][now.y] + arr[newX][newY];
//구한 인접 좌표를 큐에 넣기
q.offer(new Point(newX, newY));
check[newX][newY] = true;if(arr2[newX][newY] > arr2[now.x][now.y] + arr[newX][newY]){
arr2[newX][newY] = arr2[now.x][now.y] + arr[newX][newY];
q.offer(new Point(newX, newY));
성능 비교 :
'BOJ' 카테고리의 다른 글
| [백준 15970/java] 화살표 그리기 (0) | 2024.06.12 |
|---|---|
| [백준 9663번/java] N-Queen (0) | 2024.06.11 |
| [백준 1074번/java] Z (0) | 2024.05.11 |
| [백준 1463번/JAVA] 1로 만들기 (0) | 2024.04.09 |
| [백준 1003/JAVA] 피보나치 함수 (0) | 2024.03.31 |