글 읽기 - dfs 잘못 이해한 건가요?

papayetoo 4년 전 0

i 에서 j로 가는 경로가 있다면(arr[i][j]가 1)이라면 j 에서 k로 가는 경로가 있는 지 검사하고 (arr[j][k] == 1 ?) 경로가 존재한다면 arr[i][k] = 1로 갱신하도록 하고 있습니다.

테스트 케이스는 문제 없이 돌아가는 데 어디서 오류가 있는지 잘 모르겠습니다.

//
//  11403.cpp
//  Cpp_practice
//
//  Created by 최광현 on 2020/01/12.
//  Copyright © 2020 최광현. All rights reserved.
//

#include <iostream>
#include <queue>
#define MAX 100
using namespace std;

void dfs(int arr[][MAX], int row, int col, int size ,int visitedp[MAX]);
void printArr(int arr[][MAX], int size);

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    int arr[MAX][MAX];
    int visited[MAX]; fill(visited, visited + MAX, 0);
    for(int row = 0; row < n ; row++){
        for(int col = 0; col < n; col++)
            cin >> arr[row][col];
    }
    
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j++)
            dfs(arr, i, j, n, visited);
        fill(visited, visited + MAX, 0);
    }
    printArr(arr, n);
    
    return 0;
}

void dfs(int arr[][MAX], int row, int col, int size,int visited[MAX]){
    
    if(visited[row])
        return;
    

    for(int k = 0; k < size; k++){
        if(arr[row][col] & arr[col][k]){
            visited[k] = 1;
            dfs(arr, col, k, size, visited);
            arr[row][k] = 1;
        }
    }
    
}


void printArr(int arr[][MAX], int size){
    for(int i = 0; i < size; i++){
        for(int j = 0 ; j < size; j++)
            cout << arr[i][j] << " ";
        cout <<"\n";
    }
    
}

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

문제

문제

출처

ICPC

dfs 잘못 이해한 건가요?

papayetoo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말