글 읽기 - 50%에서 틀렸다고 나오는데 어떤것이 문제인가요?

zas777 4년 전 0

bfs로 해결하고 dfs로 해결하려는데 비슷하게 dfs형식으로 고치니까 틀렸다고 나오더 라고요..

50%에서요 어떤게 문제인가요??

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int fri[101][101];
int visit[101];
int conn[101];
int res[101];
int res_bfs[101];
int n,m;
void dfs(int idx){//가중치가 1인 최단경로-->dfs
	int x=idx;
	visit[x]=1;
	for(int i=1;i<=n;i++){
		if(visit[i]==0&&fri[x][i]==1){
			visit[i]=1;
			conn[i]=conn[x]+1;
			dfs(i);
		}
	}
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		fri[a][b]=1;
		fri[b][a]=1;
	}
	for(int i=1;i<=n;i++){
		dfs(i);
		for(int j=1;j<=n;j++){
			res_bfs[i]+=conn[j];//방법의 갯수
		}
		memset(visit,0,sizeof(visit));
		memset(conn,0,sizeof(conn));
	}
	int ans=987654321;
	int index=0;
	for(int i=1;i<=n;i++){
		if(ans>res_bfs[i])
		{
			ans=res_bfs[i];
			index=i;
		}

	}
	cout<<index<<'\n';
	return 0;
}

wjsqjawns 4년 전 3

BFS와 DFS의 차이때문입니다.

해당 문제에서 바라는 것은, 출발지점으로부터 각 노드까지의 최단 거리입니다.

BFS는 너비 우선 탐색으로, BFS의 방문 순서는 가중치를 1로 두는 해당 문제에 알맞습니다.

하지만 DFS는 그렇지 않습니다.

간단하게 예를 들어보죠.

3 3

1 2

2 3

1 3

만약 위와 같은 입력이 들어오게 된다면, 1번 노드를 기준으로

BFS라면 2까지 거리가 1, 3까지 거리가 1입니다.

하지만 DFS라면 2(혹은 3)까지의 거리가 1이면, 3(혹은 2)까지의 거리는 2가 됩니다.

위의 코드는 방문 여부를 확인하므로, 값의 갱신도 이루어지지 않습니다.

이게 문제가 되어 틀리는 것 같네요.

zas777 4년 전 0

댓글 감사합니다.

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

문제

문제

출처

ICPC

50%에서 틀렸다고 나오는데 어떤것이 문제인가요?

zas777 4년 전 0

wjsqjawns 4년 전 3

zas777 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말