[프로그래머스 Lv.0] 안전지대 C++

문제

 

폭탄과 폭탄을 둘러싼 지역을 제외한 지역의 갯수를 return하는 문제.

 

계획 세우기

n은 1이상 100 이하이기 때문에 board의 최대 크기는 100*100이 된다.

board를 완전탐색(2중 반복문을 이용)? 한다면 10000*10000번, 즉 100,000,000번 연산하게 된다. 제한 사항에 시간제약이 없기 때문에 이 방법을 써도 문제가 없을 것 같다.

 

하지만 이런 유형의 문제에서 주로 dfs/bfs를 사용했던 거 같다. dx, dy 좌표를 이용해서 board 범위를 벗어나지 않을 시 해당 경로를 선택하는 느낌의 알고리즘이었던 거 같다.

비슷한 문제

백준 2178번 미로 탐색  https://www.acmicpc.net/problem/2178

백준 7576번 토마토 https://www.acmicpc.net/problem/7576

백준 2667번 단지번호 붙이기 https://www.acmicpc.net/problem/2667

백준 4963번 섬의 개수 https://www.acmicpc.net/problem/4963

이 방법은 나중에 dfs/bfs가 뭔지 완벽하게 알면 다시 풀어보고 싶다... 그냥 아래에 풀었던 방법에서 queue만 쓰면 BFS라고 할 수 있는 건가? 아직 dfs/bfs는 다른 사람의 풀이를 보고 이해하는 정도의 단계인 거 같다...

첫 번째 풀이(구현, 완전탐색): 실패

#include <string>
#include <vector>

using namespace std;

void Check(vector<vector<int>> board, int i, int j){
    // (i-1, j-1) (i-1, j) (i-1, j+1)
    // (i, j-1)   (i, j)   (i, j+1)
    // (i+1, j-1) (i+1, j) (i+1, j+1)
    for(int a =i-1;a<=i+1;a++){
        for(int b=j-1;b<=j+1;b++){
            if(a<0 || b<0 || a>=board.size() || b>=board[0].size()) continue;
            if (a==i && b==j) continue;
            board[a][b] = 2;
        }
    }
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    for (int i=0;i<board.size();i++){
        for(int j=0;j<board[0].size();j++){
            if(board[i][j]==1) Check(board, i, j);
        }
    }
    
    for (int i=0;i<board.size();i++){
        for(int j=0;j<board[0].size();j++){
            if(board[i][j]==0) answer++;
        }
    }
    
    return answer;
}

 

프로그래머스에서 주어진 3개 예제를 실행했는데, 답이 다르게 나와서 vscode로 옮겨서 풀어야겠다고 생각했는데 마침 vscode가 고장이 났다고 해야하나... 코드를 적을 수는 있는데 디버그나 실행이 되지 않아서 그걸 고치고, BFS의 이동방식?(dx, dy를 이용한 탐색)을 적용시켜서 코드를 다시 짜보았다. 

 

 

두 번째 시도(완전탐색 그런데 dx, dy를 이용한): 실패

#include <string>
#include <vector>

using namespace std;

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

int solution(vector<vector<int>> board) {
    for (int i =0; i<board.size();i++){
        for (int j =0;j<board[0].size();j++){
            if(board[i][j] == 1){ 
                // i j를 감싼 8개의 칸 = 2로 설정 **단 벡터의 범위를 넘어가지 않을 때만
                for (int k =0;k<8;k++){
                    int nx = i+dx[k];
                    int ny = j+dy[k];
                    if(nx<0 || ny<0 || nx>board.size() || ny>board[0].size()) continue;

                    if (board[nx][ny] == 0) board[nx][ny] = 2;
                }
            }
        }
    }

    int answer =0;
    for (int i =0; i<board.size();i++){
        for (int j =0;j<board[0].size();j++){
            if(board[i][j] == 0) answer++;
        }
    }
    return answer;
}

위와 같은 에러가 떠서 예제 3 [[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]] 이 돌아가지 않았다.

저기서 에러가 난 걸 보니 뭔가 board 범위를 벗어난 nx, ny에 접근한 것 같아서 다시 보니 nx>=board.size() 였어야 범위를 벗어나지 않았다. 그 부분을 수정해주니 정답처리 되었음!

 

두 번째 방법(수정): 성공

#include <string>
#include <vector>

using namespace std;

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

int solution(vector<vector<int>> board) {
    for (int i =0; i<board.size();i++){
        for (int j =0;j<board[0].size();j++){
            if(board[i][j] == 1){ 
                // i j를 감싼 8개의 칸 = 2로 설정 **단 벡터의 범위를 넘어가지 않을 때만
                for (int k =0;k<8;k++){
                    int nx = i+dx[k];
                    int ny = j+dy[k];
                    if(nx<0 || ny<0 || nx>=board.size() || ny>=board[0].size()) continue;

                    if (board[nx][ny] == 0) board[nx][ny] = 2;
                }
            }
        }
    }

    int answer =0;
    for (int i =0; i<board.size();i++){
        for (int j =0;j<board[0].size();j++){
            if(board[i][j] == 0) answer++;
        }
    }
    return answer;
}

 

 

다른 사람 풀이

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board) {
    int answer = 0;

    const int n = board.size();
    const int m = board[0].size();
    vector<vector<int>> offset{{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}};

    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            bool passed = true;
            for(const auto& v : offset)
            {
                int ni = i + v[0];
                int nj = j + v[1];
                if(ni >= 0 && ni < n && nj >= 0 && nj < m)
                {
                    if(board[ni][nj] == 1)
                    {
                        passed = false;
                        break;
                    }
                }
            }

            answer += passed;
        }
    }

    return answer;
}

이쪽이 조금 더 정리된 방법 같은 느낌이다!