Baekjoon 3108번 로고

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

struct node{
    int n, s, w, e;
    node(){ n = s = w = e = 0; }
};

int visited[1001][1001];
node plane[1001][1001];
vector<pair<int, int>> start;

void bfs(int x, int y){
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    visited[x][y] = 1;
    while(!q.empty()){
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();
        node tmp = plane[cx][cy];
        if(tmp.n && !visited[cx-1][cy]){
            visited[cx-1][cy] = 1;
            q.push(make_pair(cx-1, cy));
        }
        if(tmp.s && !visited[cx+1][cy]){
            visited[cx+1][cy] = 1;
            q.push(make_pair(cx+1, cy));
        }
        if(tmp.w && !visited[cx][cy-1]){
            visited[cx][cy-1] = 1;
            q.push(make_pair(cx, cy-1));
        }
        if(tmp.e && !visited[cx][cy+1]){
            visited[cx][cy+1] = 1;
            q.push(make_pair(cx, cy+1));
        }
    }
}

int solve(){
    int ans = 0;
    memset(visited, 0, sizeof(visited));
    for(int i = 0; i < start.size(); i++){
        int x = start[i].first;
        int y = start[i].second;
        if(!visited[x][y]){
            bfs(x, y);
            ans++;
        }
    }
    node tmp = plane[500][500];
    if(tmp.n || tmp.s || tmp.w || tmp.e) return ans-1;
    else return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int x1, y1, x2, y2;
    for(int i = 0; i < n; i++){
        cin >> x1 >> y1 >> x2 >> y2;
        x1 += 500;
        y1 += 500;
        x2 += 500;
        y2 += 500;
        // row
        for(int y = y1; y < y2; y++){
            plane[x1][y].e = 1;
            plane[x2][y].e = 1;
        }
        for(int y = y2; y > y1; y--){
            plane[x1][y].w = 1;
            plane[x2][y].w = 1;
        }
        // col
        for(int x = x1; x < x2; x++){
            plane[x][y1].s = 1;
            plane[x][y2].s = 1;
        }
        for(int x = x2; x > x1; x--){
            plane[x][y1].n = 1;
            plane[x][y2].n = 1;
        }
        start.push_back(make_pair(x1, y1));
    }
    cout << solve();
    return 0;
}

연결 성분의 개수를 구하는 그래프 탐색 문제이다. 한가지 유의할 점은 거북이의 처음 위치인 (0, 0) 좌표를 지나는 직사각형이 있다면 결과값에서 1을 빼주어야 한다.