글 읽기 - c++ DFS 어디서 실수 했는지 모르겠습니다

sirulee5208 2년 전 0

방문하지 않았으며 1인 노드를 참조했을 때 답의 개수를 늘리고 DFS를 통해서 연결된 1, 또는 가장자리의 0을 모두 방문 처리하는 식으로 짜봤는데 어디서 실수를 했을까요?? ㅠㅠ

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> adj = { {-1,0}, {0,1}, {1,0}, {0,-1} }; //상하좌우
int m, n, k;
bool farm[51][51] = { 0, };
bool visited[51][51] = { 0, };

bool valid(int x, int y) {
    if (x > -1 && x < m && y > -1 && y < n) return true;  // 해당 좌표가 올바른 범위 안인지 확인
    else return false;
}

void dfs(int x, int y) {
    visited[x][y] = true; //방문 됨
    for (auto cord : adj) {
        int adjx = x + cord.first;
        int adjy = y + cord.second;
        if (valid(adjx, adjy)) { 
            if (!visited[adjx][adjy] && farm[adjx][adjy] == 1) { //인접 노드가 방문하지 않은 1일 시에
                dfs(adjx, adjy); //DFS
            }
            else {
                visited[adjx][adjy]=true; //인접한 0은 그냥 방문 처리
            }
        }
    }
}

int solution() {
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            //방문하지 않은 1을 발견했을 때
            if (!visited[i][j] && farm[i][j] == 1) {
                ans++;  // 답 증가
                dfs(i, j); //DFS
            }
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> m >> n >> k;
        memset(farm, false, sizeof(farm));             //초기화
        memset(visited, false, sizeof(visited));       //초기화
        while (k--) {
            int x, y;
            cin >> x >> y;
            farm[x][y] = 1;
        }
        cout << solution();
    }
    return 0;
}

dldyddlwl 2년 전 1

cout 줄 바꿈을 해주세요!! \n

sirulee5208 2년 전 0

감사합니다 ㅠㅠ 제일 단순한 거였네요...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ DFS 어디서 실수 했는지 모르겠습니다

sirulee5208 2년 전 0

dldyddlwl 2년 전 1

sirulee5208 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말