[백준 14716 - C++] 현수막 : DFS

www.acmicpc.net/problem/14716

14716번: 현수막

문제

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

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

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

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

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

 

입력

첫 번째 줄에는 현수막의 크기인 M와 N가 주어진다. (1 ≤ M, N ≤ 250)

두 번째 줄부터 M+1 번째 줄까지 현수막의 정보가 1과 0으로 주어지며, 1과 0을 제외한 입력은 주어지지 않는다.

 

출력

혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라.

 

풀이

예제 입력의 경우 이렇게 3개의 글자가 형성되게 된다.

여기서는 상하좌우 + 대각선의 경우 모두 이웃하는 것으로 보기때문에 8가지의 이동이 가능하다.

아직 방문하지 않았으며 map[]의 값이 1인 경우에만 dfs탐색을 시작한다. dfs함수안에선 8개의 이동에 대해 map의 범위를 넘어가지 않는지 확인하고 넘어가지 않는 경우에만 방문여부와 map의 값이 1인지 확인한다. 그런뒤 방문하지 않았고 map의 값이 1인 경우에만 재귀호출로 dfs함수를 호출한다. 재귀가 끝나 다시 main으로 돌아오는 경우 하나의 글자를 확인한것으로 보아 cnt의 값을 1 증가시키고 나머지 아직 방문하지 않은 map에 대해 동일한 수행을 반복한다.

 

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int X[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int Y[8] = {0, 0, 1, -1, 1, -1, 1, -1};

int map[250][250];
int visited[250][250];
int cnt;

void dfs(int x, int y, int m, int n);

int main(void){
    int m, n;
    scanf("%d %d", &m, &n);
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &map[i][j]);
        }
    }
    for(int i=0 ;i<m; i++){
        for(int j=0; j<n; j++){
            if(visited[i][j] == 1 || map[i][j] == 0)
                continue;
            dfs(i, j, m, n);
            cnt++;
        }
    }
    printf("%d\n", cnt);
}

void dfs(int x, int y, int m, int n){
    int next_x, next_y;
    
    visited[x][y] = 1;
    for(int i=0; i<8; i++){
        next_x = x+X[i];
        next_y = y+Y[i];
        if(next_x < 0 || next_x >=m || next_y < 0 || next_y >= n)
            continue;
        if(visited[next_x][next_y] == 1 || map[next_x][next_y] == 0)
            continue;
        dfs(next_x, next_y, m, n);
    }
}