[백준 / BOJ] 4883 삼각 그래프 (Java)

문제

출처 : https://www.acmicpc.net/problem/4883

4883번: 삼각 그래프

N(N>=2)개의 행, 3개의 열로이루어진 삼각그래프 가있다.

삼각그래프의 각 노드는, (y,x일때) 자신의 위치기준으로 (0, -1) (-1, -1) (-1, 0) (-1, 1)위치에 있는 노드들에서 올수있다. (해당 위치에 노드가 없는경우 올수없다.)

 

각 노드에 가중치가 있을때,

(1,2)위치부터 (N,2)위치까지 가는 최소경로를 구하는 문제다.

---

풀이

다이나믹 프로그래밍으로 풀은문제다.

 

문제를 처음보고, 음수 가중치가 주어질수있다생각해서(dp로 풀경우 이 예외생각하기가 귀찮았음), 메모이제이션을 적용한 BFS로 풀려했지만, 시간초과를 맞았다.

 

결국 다이나믹 프로그래밍으로 풀었는데, 로직은 다음과 같다.

 

우선, 각 노드가 어떤 노드에서 올수있는지 확인한다. 위에서 적었듯이 (y,x)는 (y,x-1) (y-1,x) (y-1,x+1) (y-1, x-1)위치에서 올수있다.

즉, dp배열에 항상 최솟값이 업데이트된다고 가정했을때 식을 다음과 같이 생각할수있다.

 

dp[y][x] = min(dp[y][x], 이전으로 가능한 위치 + (y,x)위치에 저장되어있는 값) 

 

이제 dp배열을 채우는 순서를 생각해보자.

dp[y][x]가 항상 최소경로임이 보장되려면, 당연히 y보다 작은 위치의 dp배열들이 모두 업데이트 되어있어야할것이다.

다시말해서, 1...y-1위치까지를 행으로 갖는 dp배열의 열들이 모두 업데이트 되어있어야한다는것이다.

이제 x값을 채우는 순서를 생각해보자.

열을 기준으로 (y값의 변동없이 x만 이동하는경우) 증가하는 경우는 (y,x+1)경우밖에없다 즉, dp[y][x]가 항상 최솟값임이 보장되려면, 1...x-1까지의 dp배열이 모두 업데이트 되어있어야한다.

 

따라서 최종 점화식은 다음과 같다.

    public int solve(int y){
        for(int x = 1; x <= 3; x++){
            for(int dir = 0; dir < 4; dir++){
                int _y = y + dy[dir];
                int _x = x + dx[dir];
                if(_x < 1 || _x > 3) continue;
                dp[y][x] = Math.min(dp[_y][_x]+arr[y][x],dp[y][x]);
            }
        }
        if(y == N) return dp[y][2];
        return solve(y+1);
    }

(y는 2부터 시작해서 N까지 증가한다.)

 

y를 2부터 증가시켜주는 이유는 y == 1 인경우를 예외처리해줘야하기때문이다.

시작위치는 항상(1,2)이며, 이 때문에, (1,1)위치에 있는 값은 절대로 참조할수없다. 하지만, (1,3)위치는 참조할수있다 만약 (1,3)위치가 음수라면 시작지점에서 (1,3)위치를 거친후 내려오는것이 이득일수있기때문에 예외처리를 통해 업데이트 해줘야한다.

---

소스코드

https://github.com/devxb/JJUNalgo/blob/master/4883%20%EC%82%BC%EA%B0%81%20%EA%B7%B8%EB%9E%98%ED%94%84/Main.java

devxb/JJUNalgo