백준 2169 JAVA

문제 유형

• DP

문제 접근

• 답
  • N,M 좌표로 도착했을 때, 최대 가치 얻기
• 주어지는 정보
  • Map 최대 크기 1,000,000 (N*M)
  • 각 좌표의 가치 -100 ~ 100
  • Move는 오른쪽, 왼쪽, 아래 방향만 가능
• 정보 정리
  • 완전 탐색
    • 시도했으나 실패
  • 남는 후보
    • 그리디 : 불가능
      • 인접한 좌표에 대한 최선의 값을 찾을 시, 최대값은 구할 수 없음
    • DP : 가능
      • https://velog.io/@mong7399/java-2169번-로봇-조종하기
• DP
  • Move의 방향이 오른쪽, 아래, 왼쪽만 가능하다는 것을 응용한다
  1. 이동 지점에 대해서, 1, 2번 방향 중 더 높은 값을 저장한다 

temp[0][0] = dp[i-1][0] + map[i][0];
for(int j = 1; j<M; j++)
{
    temp[0][j] = Math.max(dp[i-1][j], temp[0][j-1]) + map[i][j];
}

 

    2. 이동 지점에 대해서, 1, 2번 방향 중 더 높은 값을 저장한다

temp[1][M-1] = dp[i-1][M-1] + map[i][M-1];
for(int j = M-2; j>=0; j--)
{
    temp[1][j] = Math.max(dp[i-1][j], temp[1][j+1]) + map[i][j];

 

   3. 1, 2단계 중에서 더 높은 값을 최종 값으로 지정한다

for(int j = 0; j<M; j++)
{
    dp[i][j] = Math.max(temp[0][j], temp[1][j]);
}

 

 

코드

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


public class Main {
    static int N,M;
    static int[][] map;
    static int[][] dp;
    static int[][] temp;

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        dp = new int[N][M];
        temp = new int[2][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());
            }
        }

        //accumulate
        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++)
        {
            temp[0][0] = dp[i-1][0] + map[i][0];
            for(int j = 1; j<M; j++)
            {
                temp[0][j] = Math.max(dp[i-1][j], temp[0][j-1]) + map[i][j];
            }

            temp[1][M-1] = dp[i-1][M-1] + map[i][M-1];
            for(int j = M-2; j>=0; j--)
            {
                temp[1][j] = Math.max(dp[i-1][j], temp[1][j+1]) + map[i][j];
            }

            for(int j = 0; j<M; j++)
            {
                dp[i][j] = Math.max(temp[0][j], temp[1][j]);
            }

        }

        System.out.println(dp[N-1][M-1]);
    }
}

 

 

 

실패 방법

• DFS + 완전 탐색
• 이유
  • 시간 초과
    • 기본 탐색 횟수 : 3^(1,000,000) = 3방향 MOVE* (N*M)
    • accumMap(누적 가치 기록 맵)을 통해, 해당 지점으로 이동할 때의 가치값이 더 크지 않으면 이동을 중지하는 식으로 연산을 낮추려했음
    • 하지만 기본적인 탐색 횟수가 너무 많아서 시간 초과가 난 듯 함.

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


public class Main {
    static int N,M;
    static int[][] map;
    static int[][] accumMap;
    static int[][] move = {{0,1},{0,-1},{1,0}};
    static boolean[][] visited;
    static int MIN = -99999999;
    static int result = MIN;
    
    public static void dfs(int y, int x)
    {
        if(y == N-1 && x == M-1)
        {
            return;
        }
        
        for(int i = 0; i<3; i++)
        {
            int moveY = y + move[i][0];
            int moveX = x + move[i][1];
            
            if(moveY < 0 || moveY >= N || moveX < 0 || moveX >= M || visited[moveY][moveX] == true)
            {
                continue;
            }
            
    
            if(accumMap[moveY][moveX] >= accumMap[y][x] + map[moveY][moveX])
            {
                continue;
            }

            accumMap[moveY][moveX] = accumMap[y][x] + map[moveY][moveX];
            visited[moveY][moveX] = true;
            dfs(moveY,moveX);
            visited[moveY][moveX] = false;
        }
    }

    public static void PrintaccumMap(){
        for(int i = 0; i<N; i++)
        {
            for(int j = 0; j<M; j++)
            {
                System.out.print(accumMap[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        accumMap = new int[N][M];
        visited = new boolean[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());
            }
        }
        
        accumMap[0][0] = map[0][0];
        visited[0][0] = true;
        dfs(0,0);
        System.out.println(accumMap[N-1][M-1]);

        //PrintaccumMap();
    }
}