SWEA - 1868 파핑파핑 지뢰찾기

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc

SW Expert Academy

최소의 클릭수로 지뢰찾기 게임을 완료하는 문제였다.

 

문제 풀이

처음에 각 testcase마다 map과 visit vector를 매번 새로 만들어 초기화하면서 풀었는데 시간초과가 났다. dfs나 bfs로 완전탐색을 해야만 풀리는 문제 같은데 대체 어디서 초과가 나는 것인지를 모르겠어서 isInsid(), changeMap()과 같은 함수를 그냥 main과 dfs에서 풀어쓰고, 최대한 빨리 if문을 탈출하고 최대한 적게 탐색하도록 순서도 신경써줬다. 그런데도 시간 초과가 해결되지 않아서 N이 300인 testCase 한 개만을 dfs 부분을 제외하고 돌려봤다. 그런데 입력받을 때 지뢰일 경우 map을 바꿔주는 곳에서도 시간 초과가 나서 입력받을 때 map을 변화시키지 않고 모든 맵을 탐색하면서 주변이 안전한지 확인하고, 안전하다면 dfs를 하도록 고쳤다. 그런데도 시간 초과가 나서 이런 부분에서 나는 것이 아닌가..? 하는 생각을 했다.

 

혹시나 싶어서 visit와 map을 전역변수로 바꾼 후, 배열로 바꾸고 fill 함수로 초기화해주니 시간 초과가 나지 않았다..! 아마 vector로 선언하고 fill로 초기화해도 동일한 결과가 나올 것 같다.

 

시간 초과가 나는 부분을 확인하고 수정한 다음, 원래대로 입력받을 때 map을 저장하도록 문제를 푸니 통과됐다. 사실 초기화 할 때 새로 생성해서 덮어씌우는 방법과 fill로 채우는 방법에 걸리는 시간이 왜 다른지 잘 모르겠지만 앞으로는 초기화할 때 귀찮더라도 fill을 이용해야겠다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

int N;

int visit[301][301];
int map[301][301];

int dx[8] = {0,0,1,-1,-1,1,-1,1};
int dy[8] = {1,-1,0,0,1,1,-1,-1};
int visitNum;

void printVisit(){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            printf("%d ",visit[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void printMap(){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
    printf("\n");    
}

void dfs(int x, int y){    
    visit[x][y] = 1;
    visitNum++;

    for(int i=0;i<8;i++){ 
        int nx = x+dx[i];
        int ny = y+dy[i];
        
        if(nx < N && ny < N && nx >= 0 && ny >= 0 && visit[nx][ny] == 0){
            if(map[nx][ny] == 0){
                dfs(nx,ny);
            }    
            else{
                visit[nx][ny] = 1;
                visitNum++;
            }
        }      
    }    
}

int main(int argc, char** argv)
{
   int test_case;
   int T;

   cin>>T;

   for(test_case = 1; test_case <= T; ++test_case)
   {
        cin>>N;                            
       	fill(&visit[0][0], &visit[300][300], 0);
        fill(&map[0][0], &map[300][300], 0);

        int answer = 0;
        visitNum = 0;

        for(int i=0;i<N;i++){
            string str;
            cin >> str;
         for(int j=0;j<str.size();j++){
                if(str[j]=='*') {
                    map[i][j] = -1;                
                    visit[i][j] = -1;
                    visitNum++;
                    for(int k=0;k<8;k++){
                        int nx = i+dx[k];
                        int ny = j+dy[k];                
                        if(nx < N && ny < N && nx >= 0 && ny >= 0 && map[nx][ny] != -1){
                            map[nx][ny]++;
                        }
                    }
                }
            }
        }
       
       //printMap();
 
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(map[i][j] == 0 && visit[i][j] == 0){
                    dfs(i,j);
                    answer++;
                }
            }
        }
       //printVisit();
        int remainVisitNum = N*N - visitNum;
        //printf("visitNum: %d remainVisitNum: %d dfsNum: %d\n",visitNum, remainVisitNum, answer);
        answer+= remainVisitNum;
        printf("#%d %d\n",test_case, answer);
   }
   return 0;
}