백준 1149번 BFS 메모리 초과(java)

접근

이 문제는 집을 칠하는데 전집이랑 다른 색으로 칠하면 되는 문제이다.
그러나 다른 색으로 칠하되 비용이 적게 들도록 칠하는 것이다.
색은 총 3가지로 RGB이며 각 집에 따라, 색에 따라 가격이 다르다.

처음에 BFS로 접근했으나
아무래도 Queue에 무한대로 쌓이다 보니까 메모리 초과가 발생했다.
왜냐하면 들렸다 온 곳에 대한 check배열을 선언할 수가 없기 때문이다.

만약에
R:1
G:2
B:3
이라고 가정하고 3번째 집까지 일단 칠했다고 하자.

1-2-3
1-2-1

1-3-1
1-3-2

두개가 같다. 하지만 이 두개가 같다고 해서 하나만 넣을 수 없다.
왜냐하면 3번째 집이 2이면 4번째 집은 1과 3을, 3이면 4번째 집은 1과 2를 선택할 수 있는데 어떤 곳에서 최소비용이 나오는지도 모르는 채 삭제할 수 없기 때문이다.

따라서 BFS와 같이 마지막에 최종적으로 최소비용을 선택하는 방법이 아니라(이렇게 해도 되지만 상태를 체크할 수 있는 조건 없이 무한대로 넣으면 메모리 초과가 발생)

동적계획법을 통해서 각 집을 칠할 때마다 최소를 선택하도록 단계마다
최적의 선택을 하도록 바꿔야 한다.

풀이과정

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

public class Main {
    static int[][] color_cost;
    static int min;



    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        color_cost = new int[N + 1][4];



        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j <= 3; j++) {
                color_cost[i][j] = Integer.parseInt(st.nextToken());
            }

        }

        for(int i=2;i<=N;i++){
            color_cost[i][1]+= Math.min(color_cost[i-1][2],color_cost[i-1][3]);
            color_cost[i][2]+= Math.min(color_cost[i-1][1],color_cost[i-1][3]);
            color_cost[i][3]+= Math.min(color_cost[i-1][1],color_cost[i-1][2]);
        }

        min = Integer.MAX_VALUE;
        for(int i=1;i<=3;i++){
            if(min>color_cost[N][i])
                min= color_cost[N][i];
        }

        bw.write(Integer.toString(min));
        bw.flush();
        bw.close();
        br.close();


    }
}