[백준: Java] 2169 - 로봇 조종하기

[문제]

https://www.acmicpc.net/problem/2169

 

처음에는 다익스트라를  생각하고 문제에 접근했으나, 모든 정점을 확인할 수 없어 dp로 풀어낸 문제입니다.

 

dp 문제답게 풀이가 길지 않습니다.

 

또한 코드트리에서 연습했던 dp 빈출 유형과 유사한 문제였습니다.

---

[초기화]

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, m;
	static int[][] map;
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		solve();
	}

---

[풀이]

	static void solve() {
		int[][] dp = new int[n][m];
		for(int i = 0; i < n; i++)
			Arrays.fill(dp[i], -100);
		
		dp[0][0] = map[0][0];
		
		for(int i = 1; i < m; i++)
			dp[0][i] = dp[0][i - 1] + map[0][i];
		
		for(int i = 1; i < n; i++) {
			int[] left = new int[m];  // 각 행에 대한 열의 값을 저장할 배열
            int[] right = new int[m];
            
            left[0] = dp[i - 1][0] + map[i][0];  // 왼쪽 끝 아래로 내려와서
			for(int j = 1; j < m; j++) {  // 오른쪽 이동
				left[j] = map[i][j] + Math.max(left[j - 1], dp[i - 1][j]);
			}
			
			right[m - 1] = dp[i - 1][m - 1] + map[i][m - 1];  // 오른쪽 끝 아래로 내려와서
			for(int j = m - 2; j > -1; j--) {  // 왼쪽 이동
				right[j] = map[i][j] + Math.max(right[j + 1], dp[i - 1][j]);
			}
			
			for(int j = 0; j < m; j++)
				dp[i][j] = Math.max(left[j], right[j]);  //  왼쪽 이동과 오른쪽 이동 중 큰 값
		}
		
		System.out.println(dp[n - 1][m - 1]);
	}

먼저 dp 배열을 최솟값으로 초기화한 후, 기본값(시작 위치의 값)을 설정합니다.

 

이후 첫 행 기준으로 값을 오른쪽 방향으로 이동하며 누적합니다.

해당 값만 처리하는 이유는 첫 행에서 갈 수 있는 방향은 오른쪽뿐이며, 이미 지나간 곳은 다시 방문할 수 없기 때문입니다.

 

이후 로직은 다음과 같습니다.

1. 다음 행부터 왼쪽 이동값과 오른쪽 이동값을 미리 계산
   • 위쪽과 지나온 값 중에 최대가 되는 값 선택
2. 값들의 계산이 전부 끝나면 현재 위치에서 최대가 되는 값 선택
   • 모든 순회가 끝나면 해당 행 완성

---

[전체 코드]

package 백준.골드;

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

public class BOJ_2169_로봇조종하기 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, m;
	static int[][] map;
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		solve();
	}
	
	static void solve() {
		int[][] dp = new int[n][m];
		for(int i = 0; i < n; i++)
			Arrays.fill(dp[i], -100);
		
		dp[0][0] = map[0][0];
		
		for(int i = 1; i < m; i++)
			dp[0][i] = dp[0][i - 1] + map[0][i];
		
		for(int i = 1; i < n; i++) {
			int[] left = new int[m];  // 각 행에 대한 열의 값을 저장할 배열
            int[] right = new int[m];
            
            left[0] = dp[i - 1][0] + map[i][0];  // 왼쪽 끝 아래로 내려와서
			for(int j = 1; j < m; j++) {  // 오른쪽 이동
				left[j] = map[i][j] + Math.max(left[j - 1], dp[i - 1][j]);
			}
			
			right[m - 1] = dp[i - 1][m - 1] + map[i][m - 1];  // 오른쪽 끝 아래로 내려와서
			for(int j = m - 2; j > -1; j--) {  // 왼쪽 이동
				right[j] = map[i][j] + Math.max(right[j + 1], dp[i - 1][j]);
			}
			
			for(int j = 0; j < m; j++)
				dp[i][j] = Math.max(left[j], right[j]);  //  왼쪽 이동과 오른쪽 이동 중 큰 값
		}
		
		System.out.println(dp[n - 1][m - 1]);
	}
}

---