LeetCode : 132. Palindrome Partitioning II (BFS+String)

String문제였는데 여기에 DP를 가미한... 

근데 글쓴이는 DP로는 도저히 풀이방법이 생각나지 않고 다른 정답코드를 봐도 이해가 잘 되지 않아..서 BFS코드를 참고해서 풀었다.

 

[메인 로직]

String+BFS로 풀었다.

맨처음 큐에 0을 넣어주고 for문으로 맨 뒤 idx부터 현재 idx까지 역순으로 탐색하며 팰린드롬이 되는 지 확인한다.

만약 팰린드롬이 완성된다면 큐에 해당 idx를 넣어주었다.

이 과정을 반복!

한 레벨이 반복될 수록 cuts가 1씩 늘어나는 것!

 

class Solution {
public:
    int visited[2001] = {0, };
    
    bool check(int Start, int End, string s){
        int half = (End+1-Start)/2; // 양쪽을 비교할 횟수
        for(int i=0; i<half; i++){
            if(s[Start+i]!=s[End-i]) return false;
        }
        return true;
    }
    
    int minCut(string s) {
        queue<int> q;
        q.push(0);
        int cuts = 0;
        
        while(1){
            int size = q.size();
            for(int i=0; i<size; i++){
                int curr = q.front();
                q.pop();
                if(visited[curr]) continue;
                                
                // curr~j까지 팰린드롬이 되는 곳을 저장
                // 맨 마지막 혼자 남아도 팰린드롬이 되기 때문에 curr값까지 포함!
                for(int j=s.size()-1; j>=curr; j--){
                    if(!check(curr, j, s) || visited[j]) continue;
                    if(j==s.size()-1){
                        return cuts;
                    }
                    q.push(j+1);
                }
                visited[curr] = true;
            }
            
            cuts++;
        }
        
        return cuts;
    }
};