백준 27211 - 도넛 행성(C++)

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

27211번: 도넛 행성

다른 BFS와 달리 map의 N번째 칸에 도달했을 때, 더 이상 이동못하는 것이 아닌, 1번째 칸으로 이동하게 됩니다.

 

이를 코드로만 짤 수 있다면 나머지는 다른 BFS문제와 같게 푸시면 됩니다.

 

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#define F first
#define S second

using namespace std;

int N, M;
int map[1001][1001];
int check[1001][1001];
int dx[4] = {1 ,0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int forest;

void bfs(int X, int Y){
    queue<pair<int, int>> q;
    q.push({X, Y});
    check[X][Y] = 1;
    while(!q.empty()){
        int x = q.front().F;
        int y = q.front().S;
        q.pop();
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx == N + 1) xx = 1;
            if(xx == 0) xx = N;
            if(yy == M + 1) yy = 1;
            if(yy == 0) yy = M;
            if(check[xx][yy] == 1) continue;
            if(map[xx][yy] == 0){
                check[xx][yy] = 1;
                q.push({xx, yy});
            }
        }
    }
}

void solve(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(map[i][j] == 0 && check[i][j] == 0){
                forest++;
                bfs(i, j);
            }
        }
    }
    cout << forest;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.