#14716번 현수막 (C++)

링크 : www.acmicpc.net/problem/14716

14716번: 현수막

 

문제풀이는 다음과 같다.

 

(1) 배열의 첫 지점부터 끝 지점까지 for문을 돌린다. 

(2) 해당 지점을 방문한 적이 없으며(false), 1의 값을 가질 경우 DFS를 진행한다.

DFS를 빠져나왔을 경우를 고려하여 바로 다음 줄에는 결과값을 + 1 해주는 코드를 작성한다. 

(3) 해당 지점의 상하좌우, 대각선 방향으로 for문을 돌려서 해당 값이 값을 초과하지 않고, 방문한 경험이 없었으며(false), 1의 값을 가질 경우에 그 값을 기준으로 또 다시 dfs를 진행한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int y = 0, x = 0, ans = 0;
int my[8] = {1,1,0,1,-1,-1,0,-1};
int mx[8] = {0,1,1,-1,0,-1,-1,1};
bool check[252][252] = { false, };
int v[252][252];

bool track(int h, int w) {
    if (h<1 || h>y || w<1 || w>x || check[h][w] || v[h][w] == 0) return false;
    else return true;
}

void dfs(int h, int w) {
    check[h][w] = true;
    for (int i = 0; i < 8; i++) {
        int ny = h + my[i];
        int nx = w + mx[i];
        if (track(ny, nx)) {
            dfs(ny, nx);
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a = 0;
    cin >> y >> x;
    for (int i = 1; i <= y; i++) {
        for (int j = 1; j <= x; j++) {
            cin >> a;
            v[i][j] = a;
        }
    }
    for (int i = 1; i <= y; i++) {
        for (int j = 1;j <= x; j++) {
            if (!check[i][j] && v[i][j] == 1) {
                dfs(i, j);
                ans++;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

처음에 바로 정답은 나왔지만, 메모리와 시간이 크게 나왔다는 점이 내키지 않았다.

코드를 조금 수정하여 시간을 절반으로 단축시켰지만 메모리 크기는 감소시키지 못했다. 

(시간 단축을 위해, track(ny,nx)이전에 if(!check[ny][nx]&&arr[ny][nx]==1)을 추가했다)

 

아마 초반에 배열을 크게 잡고 그대로 진행한 것이 문제였을 것이다.

다음 부터는 vector를 통해 구현할 수 있도록 시도해봐야겠다.