백준 13700번 완전 범죄

문제 링크입니다: https://www.acmicpc.net/problem/13700

처음에는 DP로 접근했던 문제였습니다.

이론상 맞는 것 같은데 계속 인덱스 3 2 1만 왔다갔다하며 반복해서 곰곰히 생각해 본 결과 문제점을 발견했습니다.

다음에 방문한 idx가 꼭 최적의 방법을 반환하는 것이 아닌데 마치 다음에 방문하는 인덱스가 최적의 결과를 반환할 것이라고 성급하게 일반화했던 것이 큰 오류였습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100000 + 1;

const int INF = 987654321;

 

int N, S, D, F, B, K;

int building[MAX];

int cache[MAX];

 

int minPressButton(int idx)

{

        //기저 사례: 경찰서이거나 범위를 벗어나면

        if (building[idx])

                 return INF;

        if (idx<1 || idx>N)

                 return INF;

        //목적지 무사 도착

        if (idx == D)

                 return 0;

 

        int &result = cache[idx];

        if (result != -1)

                 return result;

 

        //한번의 버튼 클릭으로 앞으로 달리거나 뒤로 달린다

        result = 1 + min(minPressButton(idx + F), minPressButton(idx - B));

        return result;

}

 

int main(void)

{

        cin >> N >> S >> D >> F >> B >> K;

        for (int i = 0; i < K; i++)

        {

                 int temp;

                 cin >> temp;

                 building[temp] = 1; //경찰서 표시

        }

 

        memset(cache, -1, sizeof(cache));

 

        int result = minPressButton(S);

        if (result >= INF)

                 cout << "BUG FOUND" << endl;

        else

                 cout << result << endl;

        return 0;

}

DP로 접근한 방법은 실패했기 때문에 Queue를 이용하여 BFS 탐색을 시도했습니다.

접근 방법은 비슷했지만 모든 인덱스에 대해 시도횟수를 탐색했기 때문에 DP와 달리 AC 처리를 받을 수 있었습니다.

#include <iostream>

#include <queue>

using namespace std;

 

const int MAX = 100000 + 1;

 

int N, S, D, F, B, K;

int cnt[MAX], police[MAX], visited[MAX];

queue<int> q;

 

void BFS(int idx)

{

        q.push(idx);

 

        while (!q.empty())

        {

                 idx = q.front();

                 q.pop();

 

                 int nextB = idx - B; //뒤로 갔을 때 건물

                 int nextF = idx + F; //앞으로 갔을 때 건물

 

                 //범위 내에 있고

                 if (nextB > 0)

                 {

                         //이미 방문하지 않았고 경찰서가 아니라면

                         if (!police[nextB] && !visited[nextB])

                         {

                                 visited[nextB] = 1; //방문 표시

                                 q.push(nextB); //큐에 넣고

                                 cnt[nextB] = cnt[idx] + 1; //버튼 누른 횟수 업데이트

                         }

                 }

                 //앞으로 갔을 때도 마찬가지

                 if (nextF <= N)

                 {

                         if (!police[nextF] && !visited[nextF])

                         {

                                 visited[nextF] = 1;

                                 q.push(nextF);

                                 cnt[nextF] = cnt[idx] + 1;

                         }

                 }

        }

}

 

int main(void)

{

        cin >> N >> S >> D >> F >> B >> K;

        for (int i = 0; i < K; i++)

        {

                 int temp;

                 cin >> temp;

                 police[temp] = 1;

        }

 

        cnt[D] = -1;

        BFS(S);

        if (cnt[D] == -1)

                 cout << "BUG FOUND" << endl;

        else

                 cout << cnt[D] << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~