글 읽기 - 안되는 케이스 알려주시면 감사하겠습니다

leechhe 8년 전 0

dfs로 step == 0 일때 하나씩 카운팅 해나가는데

중복 카운팅 방지하기 위해서 항상 번호가 증가하는 방향으로 조합을 찾아 나갑니다.

어디가 잘못됐는지 알려주시면 감사하겠습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>    //priority queue
#include <functional>
#include <cmath>
#include <stack>
#include <iostream>
#include <cstdlib>
#include <limits>
#include <cstring>
#include <map>
using namespace std;
int n,m;
const int INF = (1<<31)-1;
vector<vector<bool>> adj;
//vector<bool> visited;
void dfs(int& cnt, int curNode, int step){
    if( step == 0 ){
        ++cnt;
        return;
    }
    for ( int i = curNode+1 ; i <= n ; ++i ){
        if( adj[curNode][i] )
            dfs(cnt, i, step-1);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    adj = vector<vector<bool>>(n+1, vector<bool>(n+1,true));
//    visited = vector<bool>(n+1, false);
    for( int i = 0 ; i <= n ; ++i ) adj[i][i] = false;
    for( int i = 1 ; i <= m ; ++i ){
        int a,b; scanf("%d%d",&a,&b);
        adj[a][b] = adj[b][a] = false;
    }
    int ret = 0;
    for( int i = 1 ; i <= n-2 ; ++i ){
        dfs(ret, i, 2);
    }
    printf("%d", ret);
    return 0;
}

portableangel 8년 전 3

4 1

1 4

1,2,3과 2,3,4만이 가능하므로 답은 2가 나와야 하는데 4가 나옵니다.

처음 1,2를 뽑고, 4가 2와 connect되어있으므로 4를 뽑아버리는 것이 원인입니다.

현재까지 뽑은 아이스크림의 수가 2개일 땐 두 아이스크림 모두에 대해 조건 체크를 해야 합니다.

leechhe 8년 전 0

감사합니다 :)

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

문제

문제

출처

ICPC

안되는 케이스 알려주시면 감사하겠습니다

leechhe 8년 전 0

portableangel 8년 전 3

leechhe 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말