백준 9082번 지뢰찾기

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

같은 학교 학우이신 jongwook123님 덕분에 풀 수 있었던 문제였습니다.

길이가 최대 100이 주어질 수 있고 테스트케이스 또한 최대 10번 주어질 수 있으므로 브루트포스 방식으로 접근하면 TLE가 발생한다는 것은 자명했던 문제였습니다.

따라서, 그리디하게 접근해야합니다.

알고리즘은 아래와 같습니다.

1. 확정된 지뢰의 개수를 파악하고 result 변수에 저장합니다.

2. 두번째 줄을 하나하나 확인하면서 해당 위치에 지뢰가 놓일 수 있는지 파악합니다.

a) 현재 위치에 지뢰가 하나 이상 놓일 수 있다면 가능한 지뢰의 개수를 temp 변수에 저장합니다.

b) temp에 저장된 지뢰의 개수 중 확정된 지뢰의 개수를 빼줍니다.

c) 확정된 지뢰의 개수를 빼줬을 때 0이라면 더 이상 가능한 지뢰가 없다는 뜻이므로 다음 인덱스를 확인합니다.

d) 확정된 지뢰의 개수를 빼줬는데도 1 이상이라면 ↘ ↓ ↙ 순서로 지뢰가 있는지 없는지 모르는 표시 '#'을 확정된 지뢰 표시 '*'으로 바꾼 뒤 temp를 1 빼주고 result를 1 더해줍니다.

e) d)의 과정을 temp가 0이 될 때까지 반복합니다.

3. 2번이 완료되면 result를 출력해줍니다.

4. 1~3번을 각 테스트 케이스에 대해 진행해줍니다.

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[3] = { { 1, 1 }, {1, 0}, {1, -1} }; //↘ ↓ ↙

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int test_case;

        cin >> test_case;

 

        for (int t = 0; t < test_case; t++)

        {

                 int N;

                 cin >> N;

 

                 vector<string> mine(2);

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

                         cin >> mine[i];

 

                 int result = 0;

                 int temp = 0;

                 //확정된 지뢰

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

                         if (mine[1][i] == '*')

                                 result++;

 

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

                 {

                         //temp = 가능한 지뢰 수

                         if (mine[0][i] > '0' && mine[0][i] <= '9')

                                 temp = mine[0][i] - '0';

                         else

                                 continue;

 

                         //가능한 지뢰 수에서 확정된 지뢰 수를 뺀다

                         for (int j = 0; j < 3; j++)

                         {

                                 int nextY = moveDir[j].y;

                                 int nextX = i + moveDir[j].x;

                                 if (!temp)

                                          break;

 

                                 if (0 <= nextX && nextX < N)

                                          if (mine[nextY][nextX] == '*')

                                                  temp--;

                         }

 

                         //추가적인 지뢰를 찾고 확정된 지뢰로 바꿔준다

                         for (int j = 0; j < 3; j++)

                         {

                                 int nextY = moveDir[j].y;

                                 int nextX = i + moveDir[j].x;

                                 if (!temp)

                                          break;

 

                                 if (0 <= nextX && nextX < N)

                                          if (mine[nextY][nextX] == '#')

                                          {

                                                  mine[nextY][nextX] = '*';

                                                  result++;

                                                  temp--;

                                          }

                         }

                 }

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

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