C - [백준 1926] 그림 (feat. BFS, 연결요소, 방향)

 

참조 포스트

 

2024.12.22 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 그래프 + BFS

[자료구조 & 알고리즘] 그래프 + BFS

 

2024.12.22 - [Computer Science/알고리즘 문제] - C - [Backjoon 11724] 연결 요소의 개수 (feat. 배열)

C - [Backjoon 11724] 연결 요소의 개수 (feat. 배열)

 

2024.12.25 - [Computer Science/자료구조 & 알고리즘] - C - [Backjoon 2178] 미로탐색 (feat. BFS & 최단거리 탐색)

 

 

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

 

예제 입력 1 복사

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력 1 복사

4
9

BOJ 1926: 그림 (그림 영역 크기 계산)

---

문제 설명

BOJ 1926 그림 문제는 2차원 배열에서 연결된 1들의 그룹을 "그림"으로 간주하고, 이 그림의 개수와 가장 큰 그림의 크기를 구하는 문제입니다.

문제 조건

• 입력으로 주어지는 2차원 배열에서 1은 그림을 구성하고, 0은 빈칸입니다.
• 상하좌우로 연결된 1들이 하나의 그림을 형성합니다.
• 그림의 개수와 가장 큰 그림의 넓이를 출력해야 합니다.

입력

1. 첫 번째 줄: 배열의 크기 N×MN \times M (1≤N,M≤5001 \leq N, M \leq 500)
2. 두 번째 줄부터 NN개의 줄: MM개의 0과 1로 이루어진 값

출력

1. 그림의 개수
2. 가장 큰 그림의 넓이

---

Checkpoint

 

기존의 BFS 문제 였던 (check 1) 연결요소(https://rnasterofmysea.tistory.com/48)의 연결요소 계산하는 방법과

(check 2) 최단거리 탐색(https://rnasterofmysea.tistory.com/51)의 상하좌우 탐색(x,y좌표) 방법을 합친 문제입니다.

 

1로 된 그림 부분을 연결 요소라고 생각하여 check 1 방법 적용 후 BFS 탐색 과정에서 check2 방법을 적용해서 해결하였습니다.

 

 

---

구현코드

/*
https://www.acmicpc.net/problem/1926
BOJ 1926

<Keypoint>
BFS + 최단경로 찾기 & 연결요소


연결요소로 각 그림 단위로 분할해서 처리
최단경로 찾기로 그림의 넓이 구하기
*/
#include <stdio.h>

int graph[500][500];
int visited[500][500];
int queue[250000][2];
int front, rear;

// 방향벡터: 상, 하, 좌, 우
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 큐에 추가
void enqueue(int x, int y) {
    queue[rear][0] = x;
    queue[rear][1] = y;
    rear++;
}

// 큐에서 제거
void dequeue(int *x, int *y) {
    *x = queue[front][0];
    *y = queue[front][1];
    front++;
}

// BFS 함수
int bfs(int start_x, int start_y, int n, int m) {
    int area = 0;
    enqueue(start_x, start_y);
    visited[start_y][start_x] = 1;

    while (front < rear) {
        int x, y;
        dequeue(&x, &y);
        area++;

        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[ny][nx] && graph[ny][nx] == 1) {
                enqueue(nx, ny);
                visited[ny][nx] = 1;
            }
        }
    }

    return area;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    // 그래프 입력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    int max_area = 0;
    int count = 0;

    // 전체 그래프 탐색
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (graph[i][j] == 1 && !visited[i][j]) {
                front = rear = 0; // 큐 초기화
                int area = bfs(j, i, n, m);
                if (area > max_area) {
                    max_area = area;
                }
                count++;
            }
        }
    }

    printf("%d\n%d", count, max_area);
    return 0;
}

1. 코드 개요

이 코드는 2차원 그래프에서 연결된 1들을 "그림"으로 간주하고, 그림의 개수와 가장 큰 그림의 넓이를 계산하는 문제를 해결합니다. BFS(너비 우선 탐색)를 사용하여 연결된 영역을 탐색하며, 그림의 넓이를 누적 계산합니다.

---

2. 코드 주요 구성 요소

(1) 전역 변수

• graph[500][500]: 입력으로 주어진 그래프를 저장합니다.
• visited[500][500]: 각 좌표의 방문 여부를 저장합니다.
• queue[250000][2]: BFS에서 탐색할 좌표를 저장하는 큐입니다.
• front, rear: 큐의 front와 rear를 관리합니다.

(2) 방향 벡터 (dir)

int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

• BFS 탐색 시 상, 하, 좌, 우 네 방향으로 이동하기 위해 사용합니다.

(3) 큐 구현

큐는 BFS에서 탐색할 좌표를 저장하기 위해 사용됩니다.

• enqueue(int x, int y): 큐에 새로운 좌표를 삽입합니다.
• dequeue(int *x, int *y): 큐의 front에서 좌표를 꺼냅니다.

---

3. BFS 함수

역할:

• 특정 좌표에서 BFS를 시작하여 연결된 모든 1을 탐색합니다.
• 탐색한 1의 개수를 계산하여 넓이를 반환합니다.

구현:

int bfs(int start_x, int start_y, int n, int m) {
    int area = 0;  // 현재 그림의 넓이
    enqueue(start_x, start_y);
    visited[start_y][start_x] = 1;

    while (front < rear) {  // 큐가 빌 때까지 반복
        int x, y;
        dequeue(&x, &y);
        area++;

        for (int i = 0; i < 4; i++) {  // 상하좌우 탐색
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[ny][nx] && graph[ny][nx] == 1) {
                enqueue(nx, ny);
                visited[ny][nx] = 1;
            }
        }
    }

    return area;  // 그림의 넓이 반환
}

작동 원리:

1. 시작 좌표 (start_x, start_y)에서 BFS 탐색을 시작합니다.
2. 큐에 좌표를 넣고, 해당 좌표를 방문 처리합니다.
3. 큐에서 좌표를 하나씩 꺼내며, 상하좌우를 탐색하여 연결된 1을 찾습니다.
4. 새로 발견된 1의 좌표를 큐에 추가하며 넓이를 증가시킵니다.
5. 탐색이 끝나면 해당 그림의 넓이를 반환합니다.

---

4. 메인 함수

역할:

• 전체 그래프를 탐색하며, 새로운 그림을 발견할 때마다 BFS를 호출합니다.
• 그림의 개수와 가장 큰 넓이를 계산합니다.

구현:

int main() {
    int n, m;
    scanf("%d %d", &n, &m);  // 그래프 크기 입력

    // 그래프 입력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    int max_area = 0;  // 가장 큰 그림의 넓이
    int count = 0;     // 그림의 개수

    // 전체 그래프 탐색
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (graph[i][j] == 1 && !visited[i][j]) {  // 새로운 그림 발견
                front = rear = 0;  // 큐 초기화
                int area = bfs(j, i, n, m);  // BFS 호출
                if (area > max_area) {
                    max_area = area;  // 최대 넓이 갱신
                }
                count++;  // 그림 개수 증가
            }
        }
    }

    printf("%d\n%d", count, max_area);  // 결과 출력
    return 0;
}

작동 원리:

1. 입력받은 그래프를 2중 반복문으로 순회합니다.
2. 아직 방문하지 않은 1을 발견하면, 새로운 그림으로 간주하고 BFS를 호출합니다.
3. BFS 결과로 반환된 넓이를 비교하여 최대 넓이를 갱신합니다.
4. 그림의 개수를 하나씩 증가시킵니다.
5. 모든 탐색이 끝난 후, 그림의 개수와 최대 넓이를 출력합니다.

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.