백준, BOJ, 4963번 C++ [CPP]

 

왜 DP 알고리즘 분류에 들어있는지 모를 문제

 

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

 

---

 

테스트 케이스가 많은 문제는

어차피 하나에 대해서 풀 수 있다면 모조리 풀 수 있고

ios::sync_with_stdio(0);

cin.tie(0);

을 꼭 써주자.

 

이건 그냥 따로 공부할 필요도 없다.

그냥 대각선까지 가능한 BFS를 풀면된다.

탐색을 4방향에서 8방향으로 늘리면 되는 문제다.

 

다를게 하나도 없다.

 

#맞은 풀이

#include<iostream>
#include<vector>
#include<queue>

#define X first
#define Y second

//8방향으로 이동가능 제자리 빼고
int dx[8] =  {1,1,1,0,0,-1,-1,-1};
int dy[8] =  {-1,0,1,-1,1,-1,0,1};

using namespace std;

int map[52][52];
int visit[52][52];

void init(int a[52][52]){
    for(int i=0; i<52; i++){
        for(int j=0; j<52; j++){
            a[i][j] = 0;
        }
    }
    
    return;
}

int cnt = 0; // 섬의 개수


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    while(1){
        int a,b;
        cin >> a >> b;
        
        
        //0,0 입력이면 입력받지 않고 종료
        if(a == 0 && b == 0) break;
        
        //입력받기
        for(int i=0; i<b; i++){
            for(int j=0; j<a; j++){
                cin >> map[i][j];
            }
        }
        
        //맵을 뒤져볼 queue 생성
        queue<pair<int,int>> Q;
        

        
        for(int i=0; i<b; i++){
            for(int j=0; j<a; j++){
                
                if(map[i][j] == 0 || visit[i][j] == 1)continue;
                Q.push({i,j});
                visit[i][j] = 1;
                cnt++;
                
                while(!Q.empty()){
                    auto cur = Q.front();
                    Q.pop();
                    
                    for(int dir = 0; dir<8; dir++){
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        
                        //범위체크
                        if(nx<0 || nx >=b || ny<0 || ny>=a) continue;
                        //방문했거나 map에서 0일경우
                        if(map[nx][ny] == 0 || visit[nx][ny] == 1)continue;
                        //이어져있을 경우
                        Q.push({nx,ny});
                        visit[nx][ny] = 1;
                        
                    }
                    
                }

            }
        }
        //모든 map을 다 뒤졌다면 섬 갯수 출력
        cout << cnt <<'\n';
        
        cnt = 0; // 섬 개수 초기화
        init(map); // 배열초기화
        init(visit);
    }
}

 

 

다만 여러 번의 테스트케이스이므로

값을 초기화를 잘하도록 하자.

여기서 포인트는

dx, dy를 구성하는 방법 

그외 아무것도 없다.