4677 Oil Deposit

#include <stdio.h>
#include <string.h>
 
char arr[105][105] = { 0 };
char chk[105][105] = { 0 };
 
int dx[8] = { 0,1,1,1,0,-1,-1, -1 };
int dy[8] = { 1,1,0,-1,-1,-1,0, 1 };
void dfs(int y, int x, int row, int col) {
    chk[y][x] = 1;
 
    for (int i = 0; i < 8; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        if (xx < 0 || x >= col || yy < 0 || y >= row)
            continue;
        if (chk[yy][xx] == 1 || arr[yy][xx] == '*')
            continue;
 
        dfs(yy, xx, row, col);
    }
}
 
int main() {
    while (1) {
        int row, col;
        scanf("%d %d", &row, &col);
 
        if (row == 0 && col == 0)
            break;
 
        memset(arr, 0, sizeof(arr));
        memset(chk, 0, sizeof(chk));
 
        for (int i = 0; i < row; i++) {
            scanf("%s", &arr[i]);
        }
        
        int rst = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (arr[i][j] == '@' && chk[i][j] == 0) {
                    rst++;
                    dfs(i, j, row, col);
                }
            }
        }
        printf("%d\n", rst);
    }
}
 

바로 방금 전에 풀었던 문제와 똑같은 방식으로 풀렸던 문제다.

이것도 DFS밖에 방법이 생각나질 않는데, 그 이외의 방법은 뭐가 있을지 모르겠다.