[JAVA] 백준 11048번 : 이동하기

---

 

• 코드

실패 코드 : DP 분류에 있는 문제를 눌렀는데 bfs로 풀 수 있는 문제 같아서 bfs로 구현해 보았다. 결과는 시간초과..

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[] x = { 1, 0, 1 };
	static int[] y = { 0, 1, 1 };
	static int N, M, max = 0;
	static int[][] array;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		array = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++)
				array[i][j] = Integer.parseInt(st.nextToken());
		}
		bfs(0, 0, 0);

		System.out.println(max);
	}

	static void bfs(int a, int b, int count) {
		count += array[a][b];

		if (a == N - 1 && b == M - 1) {
			if (count > max)
				max = count;
			return;
		}

		for (int direction = 0; direction < 3; direction++) {
			int r = a + x[direction];
			int c = b + y[direction];

			if (r >= 0 && c >= 0 && r < N && c < M)
				bfs(r,c,count);
		}
	}

}

 

설명 : dp문제 답게 dp로 풀었다. 사진에서 보듯이 현재 위치에서 (-1,-1), (-1,0), (0,-1) 한 위치의 값들 중 가장 큰값을 현재 위치의 값과 더 해준다. 이렇게 (N, M)까지 반복문을 돌리면 N, M 위치엔 (0, 0)위치에서 (+1,0), (0,+1), (+1, +1)하면서 더해준 값 중 가장 큰 값이 저장되어 있는다.

 

 

정답 코드 : 위에서 쓴 식으로 풀어낸 코드이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		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());
		int[][] array = new int[N+1][M+1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= M; j++)
				array[i][j] = Integer.parseInt(st.nextToken());
		}
		
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) 
				array[i][j] += Math.max(array[i-1][j-1], Math.max(array[i-1][j], array[i][j-1]));
		}
		
		System.out.println(array[N][M]);
	}

}