[백준] 11048 - 이동하기 (JAVA)

1. 소요시간 : 35분.
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 2
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/11048
8. 푼 날짜 : 2023.03.07

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.

2. 풀이과정

나의 (왼쪽), (위), (그리고 왼쪽 위) 중에서 누적된 합중 더 큰 값을 찾아서 그 값과 현재 내가 탐색하고 있는 좌표의 숫자를 더해준다.

처음에는 BFS 로 풀려고 했었는데 전체적으로 코드는 잘 수행 되었으나 메모리 초과가 났다. BFS 로 우선 풀려면 visited 배열을 사용해서는 안됐다. 이미 한 번 탐색했던 좌표를 다시 찾아 올 수 있기 때문이다. 그렇기에 한 번 좌표를 탐색할 때마다 queue에 3개를 계속 add 해줘야 했고 N,M이 1,000이니 곱해서 1,000,000 번 queue에 3번씩 add 할 수도 있었다. 그렇게 돼서 메모리 초과가 났다. 어떻게 하면 메모리 초과가 나지 않게 할 수 있을까 까지를 계속 고민했다. BFS의 풀이 자체는 변하지 않은 채로 말이다. 그렇게 30분쨰에 접어들어서 풀이를 모르겠어서 다른 사람의 풀이를 참고했다. BFS 자체를 쓰면 안 됐던 것이다. 참 DP 유형의 문제는 구상이 어렵다. 다른 사람의 풀이를 보면 간단하고도 효과적이라 가끔 현타도 오는 것 같다... ㅎ

3. 소스코드

-- 처음에 실패한 BFS 코드 --
(메모리 초과)

import java.io.*;
import java.util.*;


public class Main{
	
	static int map[][];
	static int dp[][];
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb=new StringBuilder();

		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		map=new int[N][M];
		dp=new int[N][M];
		
		for(int i=0;i<N;i++) {
			String line[]=br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				map[i][j]=Integer.parseInt(line[j]);
			}
		}
		
		bfs(0,0);
		
		System.out.println(dp[N-1][M-1]);

		
	}
	public static void bfs(int y,int x) {
		int yy[]= {0,1,1};
		int xx[]= {1,0,1};
		dp[0][0]=map[0][0];
		Queue<Integer[]> queue=new LinkedList<>();
		queue.add(new Integer[] {y,x});
		
		while(!queue.isEmpty()) {
			Integer temp[]=queue.poll();
			int prevY=temp[0];
			int prevX=temp[1];
			for(int i=0;i<3;i++) {
				int nextY=prevY+yy[i];
				int nextX=prevX+xx[i];
				if(nextY>=map.length||nextX>=map[0].length) continue;
				dp[nextY][nextX]=Math.max(dp[nextY][nextX],dp[prevY][prevX]+map[nextY][nextX]);
				
				queue.add(new Integer[] {nextY,nextX});
			}
			
		}
		
		
	}
}

(다른 사람의 풀이를 보고 푼 DP 코드)

import java.io.*;
import java.util.*;


public class Main{
	
	static int map[][];
	static int dp[][];
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb=new StringBuilder();

		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		map=new int[N+1][M+1];
		dp=new int[N+1][M+1];
		
		for(int i=0;i<N;i++) {
			String line[]=br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				map[i+1][j+1]=Integer.parseInt(line[j]);
			}
		}
	
		
		for(int i=1;i<dp.length;i++) {
			for(int j=1;j<dp[0].length;j++) {
				dp[i][j]=Math.max(dp[i-1][j],Math.max(dp[i-1][j-1],dp[i][j-1]))+map[i][j];
			}
		}
		System.out.println(dp[N][M]);
	
		
	}
}

4. 결과

중간중간 BFS 코드를 통해 풀다가 메모리 초과가 나고 이것 저것 개선해서 다시 풀어봐도 똑같았다.

5. 회고

공간복잡도 계산을 하지 않고 푼 나의 패착이다.
아마 BFS 로 풀었어도 시간 초과가 났었을 수도 있을 것 같다. 중복된 노드를 계속해서 찾기 때문에말이다.
오늘이 수요일인데 최소한 이번주 주말까지는 냅색 문제까지 도전해보겠다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212