백준 2583번 영역 구하기

#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
 
int M, N, K;
int visited[100][100];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int squarewidth;
void make(int x1, int y1, int x2, int y2) {
    for (int i = x1; i < x2;i++) {
        for (int j = y1; j < y2; j++) {
            visited[i][j] = 1;
        }
    }
}
void DFS(int y,int x) {
    //이 부분 범위 확인하는 방법 &&이 아니라 ||을 사용해야됨.
    if (y < 0 && y >= N && x < 0 && x >= M) return ;
 
    visited[y][x] = 1;
    squarewidth++;
    for (int i = 0; i < 4; i++) {
        int nexty = y + dy[i];
        int nextx = x + dx[i];
        if (0 <= nexty && nexty < N && 0 <= nextx && nextx < M) {
            if (!visited[nexty][nextx])
                DFS(nexty, nextx);
        }
    }
}
int main(void) {
    //N,M  순서변경
    cin >> M >> N >> K;
    for (int i = 0; i < K; i++) {
        int x1, y1;
        int x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        make(x1, y1, x2, y2);
    }
    vector<int> width;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visited[i][j]) {
                squarewidth = 0;
                DFS(i, j);    
                width.push_back(squarewidth);
            }
        }
    }
    //오름차순 정렬
    sort(width.begin(), width.end());
    cout << width.size() << endl;
    for (int i = 0; i < width.size(); i++)
        cout << width[i] << " ";
 
    return 0;
}

문제 출처:https://www.acmicpc.net/problem/2583

좌표만 잘 뒤집어서 생각해보면 쉽게 풀 수 있는 문제였습니다. 

DFS에서 nexty,nextx의 범위를 잘 고려해서 if문을 설정해줘야 오류없이 돌아가네요.

#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
 
int M, N, K;
int visited[100][100];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int squarewidth;
void make(int x1, int y1, int x2, int y2) {
    for (int i = x1; i < x2; i++) {
        for (int j = y1; j < y2; j++) {
            visited[i][j] = 1;
        }
    }
}
void DFS(int y, int x) {
    //기저 사례1: 범위확인
    if (y < 0 || y >= N || x < 0 || x >= M) return;
    //기저 사례2: 방문했으면 종료
    if (visited[y][x]) return;
    visited[y][x] = 1;
    squarewidth++;
    for (int i = 0; i < 4; i++) {
        int nexty = y + dy[i];
        int nextx = x + dx[i];
        DFS(nexty, nextx);
    }
}
int main(void) {
    //N,M  순서변경
    cin >> M >> N >> K;
    for (int i = 0; i < K; i++) {
        int x1, y1;
        int x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        make(x1, y1, x2, y2);
    }
    vector<int> width;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visited[i][j]) {
                squarewidth = 0;
                DFS(i, j);
                width.push_back(squarewidth);
            }
        }
    }
    //오름차순 정렬
    sort(width.begin(), width.end());
    cout << width.size() << endl;
    for (int i = 0; i < width.size(); i++)
        cout << width[i] << " ";
 
    return 0;
}

위에 코드는 오류가 있었네요. 어쩐지 범위 확인하는 방법을 1번만 적용했을 때 코드가 안하길래

왜 그런가 싶었는데 첫번째 기저사례1 범위 체크 하는 방법을 실수했었네요..  조심해야겠습니다. 

오류 수정하고나니까 훨씬 코드가 깔끔하고 보기좋아졌네요.