"백준 14716번: 현수막" 문제를 풀어보았다!

🤔 문제 설명

ANT가 처음 알고리즘 대회를 개최하게 되면서 현수막을 내걸었다.

저번 학기 영상처리 수업을 듣고 배웠던 지식을 최대한 응용 해보고 싶은 혁진이는 이 현수막에서 글자가 몇 개인지 알아보는 프로그램을 만들려 한다.

혁진이는 우선 현수막에서 글자인 부분은 1, 글자가 아닌 부분은 0으로 바꾸는 필터를 적용하여 값을 만드는데 성공했다.

그런데 혁진이는 이 값을 바탕으로 글자인 부분 1이 상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자라고 생각만 하였다.

혁진이가 필터를 적용하여 만든 값이 입력으로 주어졌을 때, 혁진이의 생각대로 프로그램을 구현하면 글자의 개수가 몇 개인지 출력하여라.

✅ 나의 풀이

DFS를 활용한 문제이고 다음 글자로 넘어가는 부분에서 살짝 힘들었다. main에서 반복문을 통해 처리하고 조건이 맞을 때 DFS 탐색을 하도록 하였다.

#include <iostream>
#include <vector>
using namespace std;

int M, N;
vector<vector<int>> board;
vector<vector<bool>> visited;

int xD[8] = {0, 1, -1, 0, 1, -1, 1, -1};
int yD[8] = {1, 0, 0, -1, 1, -1, -1, 1};

void DFS(int x, int y) {
    visited[x][y] = true; // 방문 표시

    for(int i=0;i<8;i++) {
        int xA = x + xD[i]; // 다음 위치 계산
        int yA = y + yD[i];

        if (xA >= M || yA >= N || xA < 0 || yA < 0) continue; // 범위 체크

        if (board[xA][yA] == 1 && !visited[xA][yA]) {
            DFS(xA,yA);
        }
    }

}

int main() {
    cin >> M >> N;

    board.resize(M, vector<int>(N));
    visited.resize(M, vector<bool>(N, false)); // 초기값은 모두 false로 설정

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }

   int count = 0;

   for(int i=0;i<M;i++) {
        for(int j=0;j<N;j++) {
            if (board[i][j] == 1 && !visited[i][j]) { // 현수막의 값이 '1'이고 아직 방문하지 않았다면
                DFS(i,j); // DFS 탐색 수행
                count++; // 덩어리 개수 증가
            }
        }
    }

   cout << count << endl; // sum 출력
    
}

➡️ DFS 여전히 헷갈려..ㅜ