백준 17025 - Icy Perimeter(C++)

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

17025번: Icy Perimeter

영문으로 되어있는 문제이지만 간단했습니다.

문제를 해석해보자면, '#'으로 연결된 가장 큰 그룹을 구하고, 해당 그룹의 둘레를 구하는 문제입니다.

그룹의 크기가 같다면, 둘레가 가장 작은 것이 답이 됩니다.

 

<문제 접근 과정>

1. 먼저 '#'의 값을 가진 좌표를 찾은 뒤 해당 좌표로 탐색을 시작한다.

2. 4방향 탐색을 통해서 탐색이 가능한 다음 좌표를 찾는다.

    (탐색할 수 있는 조건 -> 다음 좌표가 map 범위 안에 있어야 하면서, 이전에 방문하지 않았고, 해당 좌표의 값이 '#'이여야 한다.)

3. 다음 좌표를 찾았다면 해당 좌표로 이동하면서 그룹의 크기와 해당 좌표의 둘레를 더해줍니다.

    (해당 좌표의 둘레는 해당 좌표에서 4방향 탐색을 한 뒤, '#' 값이 없는 갯수만큼 더해주면 됩니다.)

    3-1. 좌표를 이동할 때마다 둘레를 구하는 것은 마지막에 한번에 둘레를 구하는 것과 같은 값을 도출할 수 있습니다. 

  

 

 

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

#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;
char map[1011][1011];
int check[1011][1011];
int dx[4] = {1 ,0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<pair<int, int>> Area;


bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.F > b.F) return true;
    else if(a.F == b.F){
        if(a.S < b.S) return true;
        else return false;
    }
    else return false;
}

void bfs(int X, int Y, int Size, int area){
    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 >= 1 && xx <= N && yy >= 1 && yy <= N){
                if(check[xx][yy] == 1) continue;
                if(map[xx][yy] == '#'){
                    check[xx][yy] = 1;
                    for(int j = 0; j < 4; j++){
                        int n_x = xx + dx[j];
                        int n_y = yy + dy[j];
                        if(map[n_x][n_y] != '#') area++;
                    }
                    Size++;
                    q.push({xx, yy});
                }
            }
        }
    }
    Area.push_back({Size, area});
}

void solve(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if(map[i][j] == '#' && check[i][j] == 0){
                int area = 0;
                for(int k = 0; k < 4; k++){
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(map[x][y] != '#') area++;
                }
                bfs(i, j, 1, area);
            }
        }
    }
    sort(Area.begin(), Area.end(), cmp);
    cout << Area[0].F << " " << Area[0].S;
}

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

 

 

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