[Algorithm] Baekjoon 9082번 : 지뢰찾기

https://www.acmicpc.net/problem/9082

9082번: 지뢰찾기

 

 

int t, n;
vector<string> s(2);
int arr[2][101] = { 0 };
vector<int> answers;
 
int solve()
{
    int answer = 0;
    int tempArr[2][101];
 
    memcpy(tempArr, arr, sizeof(arr));
 
    for (int i = 1; i < n - 1; ++i)
    {
        int cur = tempArr[0][i];
        int gap = cur - (tempArr[1][i - 1] + tempArr[1][i]);
 
        if (gap == 1) // 1개 더 설치해야되면
        {
            tempArr[1][i + 1] = 1;
        }
        else if (gap == 0) // 설치 안해도되면
        {
            tempArr[1][i + 1] = 0;
        }
        else return -1; // 잘못된 경우
    }
 
    for (int i = 0; i < n; ++i)
    {
        answer += tempArr[1][i];
    }
 
    return answer;
}
 
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> t;
 
    for (int i = 0; i < t; ++i)
    {
        cin >> n;
        cin >> s[0] >> s[1];
        int answer = 0;
 
        if (n == 1)
        {
            printf("%d", s[0][0] - '0');
            continue;
        }
 
        for (int i = 0; i < n; ++i)
        {
            arr[0][i] = s[0][i] - '0';
            arr[1][i] = -1;
        }
 
        if (arr[0][0] == 0)
        {
            arr[1][0] = arr[1][1] = 0;
            answer = solve();
        }
        else if (arr[0][0] == 2)
        {
            arr[1][0] = arr[1][1] = 1;
            answer = solve();
        }
        else
        {
            int answer1 = 0;
            int answer2 = 0;
 
            arr[1][0] = 0;
            arr[1][1] = 1;
            answer1 = solve();
 
            arr[1][0] = 1;
            arr[1][1] = 0;
            answer2 = solve();
 
            answer = max(answer1, answer2);
        }
 
        cout << answer << endl;
    }
 
    return 0;
}

 

예전에 풀려고 했다가 못풀었었던 문제였다. 이번엔 풀었는데, 아마 이전에 비슷한 전구켜기?문제를 했던 기억이나서 비슷한 접근을 했더니 쉽게 풀었다.

의외로 풀이법은 굉장히 쉬운데, 사실 두번쨰 문자열로주어지는 ###*## 이거는 아예 필요가 없다.

첫문자열의 첫번째 숫자에 따라 첫번째,두번째에 놓이는 지뢰가 정해진다. 

예를들어 s[0][0]이 2라면, 반드시 s[1][0]과 s[1][1]에는 지뢰가 놓이게 된다. 왜? 맨 처음의 '주변'이란, 왼쪽 없이 자기자신과 오른쪽밖에 없으니까.

그렇기 때문에 s[0][0]에 3이라는 숫자가 주어질 경우는 없다. 문제에선 반드시 되는 경우만 입력으로 주어진다고 했으니까

 

같은 이유로 s[0][0]이 0이라면, 반드시 s[1][0]과 s[1][1]에는 지뢰가 놓이지 않는다.

이렇게 처음에 s[1][0]과 s[1][1]에 지뢰여부를 알게된다면, 이후에는 간단하다. 두번째인덱스부터 끝인덱스-1까지 순회돌면서 s[0][i]값과 s[1][i-1] + s[1][i] 의 차이를 구해서 만약 1이라면 s[1][i+1]에 지뢰를 놓으면 되고 0이라면 s[1][i+1]에 지뢰를 놓지 않는게 '확정'된다.

 

근데 만약에, 처음에 s[0][0]값이 1일때는 두가지 경우로 나뉜다.

s[0][0]이 1이라면 s[1][0]이 1,s[1][1]이 0   or  s[1][0]이 0, s[1][1]이 1   이 된다.

이 두 가지경우로 나뉘기 때문에 각각 순회해서 계산해주면 된다.

 

내가 이렇게 풀었을 뿐이고, 아마 더 쉽게 하는 방법이 더 많긴한데 결국 시간복잡도가 N인건 동일하긴 하다.