1743 : 음식물 피하기 (C++)

1743번: 음식물 피하기

---

먼저 음식물이 떨어진 좌표값들을 입력 받은 후

DFS를 실행한다.

#include<iostream>

using namespace std;

#define MAX_VALUE 101

int N, M, K;
int map[MAX_VALUE][MAX_VALUE];
bool visit[MAX_VALUE][MAX_VALUE];
int cnt = 0;
int result = 0;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void dfs(int x, int y) {
    cnt++;
    visit[x][y] = true;
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx <= 0 || nx > N || ny <= 0 || ny > M) {
            continue;
        }
        if(visit[nx][ny] == false && map[nx][ny] == 1) {
            dfs(nx, ny);
        }
    }
}

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

    for(int i = 0; i < K; i++) {
        int u, v;
        cin >> u >> v;

        map[u][v] = 1;
    }

    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            if(map[i][j] == 1 && visit[i][j] == false) {
                cnt = 0;
                dfs(i, j);
                result = cnt > result ? cnt : result;
            }
        }
    }
    printf("%d\n", result);
    
    return 0;
}

 

두번째 방법은 BFS를 사용한 방식

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

#define MAX_VALUE 101

int N, M, K;
int map[MAX_VALUE][MAX_VALUE];
bool visit[MAX_VALUE][MAX_VALUE];
int cnt = 0;
int result = 0;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    visit[x][y] = true;

    cnt = 1;

    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx <= 0 || nx > N || ny <= 0 || ny > M)
                continue;
            if(visit[nx][ny] == false && map[nx][ny] == 1) {
                visit[nx][ny] = true;
                cnt++;
                q.push({nx, ny});
            }
        }
    }
}

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

    for(int i = 0; i < K; i++) {
        int u, v;
        cin >> u >> v;

        map[u][v] = 1;
    }

    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            if(map[i][j] == 1 && visit[i][j] == false) {
                cnt = 0;
                bfs(i, j);
                result = cnt > result ? cnt : result;
            }
        }
    }
    printf("%d\n", result);
    return 0;
}

아직 BFS가 많이 헷갈리는데 BFS를 사용한 방식을 연습해야 할듯.