백준 2169 로봇 조종하기 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/2169

풀이는 다음과 같다.

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

public class Main {

    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 st1 = new StringTokenizer(br.readLine());

        int R = Integer.parseInt(st1.nextToken());
        int C = Integer.parseInt(st1.nextToken());

        int[][] map = new int[R][C];
        int[][] dp = new int[R][C];
        int[][] tmp = new int[2][C]; //0이 왼->오 위->아래 중 최대, 1이 오->왼 위->아래 중 최대.

        for(int r = 0 ; r < R ; r++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for(int c = 0 ; c < C ; c++) {
                map[r][c] = Integer.parseInt(st2.nextToken());
            }
        }
        
        //처음 행은 왼 -> 오 밖에 안된다.
        dp[0][0] = map[0][0];
        for(int c = 1 ; c < C ; c++) {
            dp[0][c] = map[0][c] + dp[0][c-1];
        }


        //여기까지 초깃값, 이후 일반화



        for(int r = 1 ; r < R ; r++) {
            //오->왼, 위->아래 최대
            dp[r][0] = dp[r-1][0] + map[r][0];
            tmp[0][0] = dp[r][0];
            for(int c = 1 ; c < C ; c++) {
                tmp[0][c] = map[r][c] + Math.max(dp[r-1][c], tmp[0][c-1]);
            }

            //왼->오, 위->아래 최대
            dp[r][C-1] = dp[r-1][C-1] + map[r][C-1];
            tmp[1][C-1] = dp[r][C-1];
            for(int c = C-2 ; c >= 0 ; c--) {
                tmp[1][c] = map[r][c] + Math.max(dp[r-1][c], tmp[1][c+1]);
            }

            //tmp값중 최대
            for(int c = 0 ; c < C ; c++) {
                dp[r][c] = Math.max(tmp[0][c], tmp[1][c]);
            }
        }

        bw.write(String.valueOf(dp[R-1][C-1]));
        bw.flush();
        bw.close();
        
        
    }

}

로봇이 map을 돌아다니며 얻을 수 있는 최대 누적 값을 구하는 문제이다.

처음엔 DFS가 생각나서 아래와 같이 풀었고, 보기좋게 틀렸다.
시간초과였다.

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

public class Main {

    static int R,C;
    static boolean[][] visited;
    static int max = Integer.MIN_VALUE;
    static int answer = 0;
    static int[][] map;

    //왼쪽, 오른쪽, 아래쪽만 가능.
    static int[] dr = {1, 0, 0};
    static int[] dc = {0, -1, 1};
    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 st1 = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st1.nextToken());
        C = Integer.parseInt(st1.nextToken());
        visited = new boolean[R][C];
        map = new int[R][C];

        for(int r = 0 ; r < R ; r++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());

            for(int c = 0 ; c < C ; c++) {
                map[r][c] = Integer.parseInt(st2.nextToken());
            }
        }

        answer += map[0][0];
        DFS(0, 0);

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();


    }
    static void DFS(int r, int c) {
        if(r == R-1 && c == C-1) {
            max = Math.max(max, answer);
            return;
        }

        for(int i = 0 ; i < 3 ; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(isValid(nr, nc)) {
                visited[nr][nc] = true;
                answer += map[nr][nc];
                DFS(nr, nc);
                visited[nr][nc] = false;
                answer -= map[nr][nc];
            }
        }

    }

    


    static boolean isValid(int r, int c) {
        if(r >= 0 && r < R && c >= 0 && c < C && !visited[r][c]) return true;
        return false;
    }
}

물론 이 풀이로도 답은 나오지만, 완탐인만큼 시간초과가 나온다.
시간 제한은 1초이기 때문이다.

그래서 골머리를 앓다가 보니,
DP 문제였다.
아래의 링크에 해당 문제에 관한 자세한 DP 풀이가 있다.
나도 이 풀이를 참고하여 풀었다.
https://blog.naver.com/occidere/220808155184

알고리즘의 길은 멀고 멀다..
어려운 문제를 맞닥뜨리면 지치기도 하고,
하나의 알고리즘을 공부하다 보면
어느새 또다른 알고리즘이 내 발목을 잡는다.

하지만 아무것도 하지 않으면 아무 일도 일어나지 않는다.
계속해서 화이팅 해야겠다.