[백준] 14716번 현수막

문제 링크: https://www.acmicpc.net/problem/14716

문제

입출력

문제 접근

단순한 그래프 탐색 문제이다. 나는 dfs를 사용해서 문제를 풀었다. 탐색을 할때, 상,하,좌,우,대각선까지 9방향을 체크하면 된다. 그래프 한개당 하나의 단어로 인식해서 계산하면 되는 문제이다.

코드 구현(c++)

#include <iostream>
#include <cstring>

using namespace std;

bool check[250][250];
int map[250][250];
int wordCnt = 0;
int N, M;
int moveX[9] = {-1,0,1,-1,0,1,-1,0,1};
int moveY[9] = {-1,-1,-1,0,0,0,1,1,1};

void search(int x, int y){
    for(int i = 0 ; i < 9 ; i++){
        int nextX = x + moveX[i]; int nextY = y + moveY[i];
        if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;
        if(check[nextY][nextX] || map[nextY][nextX] == 0) continue;
        check[nextY][nextX] = true;
        search(nextX, nextY);
    }
}

void dfs(){
    for(int i = 0 ; i < M ; i++){
        for(int j = 0 ; j < N ; j++){
            if(!check[i][j] && map[i][j] == 1){
                wordCnt++;
                check[i][j] = true;
                search(j,i);
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> M >> N;
    for(int i = 0 ; i < M ; i++){
        for(int j = 0 ; j < N ; j++){
            cin >> map[i][j];
        }
    }
    memset(check, false, sizeof(check));
    dfs();
    cout << wordCnt << "\n";
}