글 읽기 - [c++] 5567번 bfs로 접근(수정)

swo98 1년 전 0

그래프를 bfs로 돌려서 1번과 간선의 거리가 최대2인 노드들에 대해서만 bfs를 진행해주고

방문한 노드를 count해주는 방식으로 접근했습니다.

특이한게 출발점(dist[1])을 1로 해주면 정답이고, 0으로 해주면 오답이 나오네요

(0으로 해주면 모든 노드들을 count함)

출발점을 0으로 해준 다음 풀고싶은데 어떻게 고쳐야할지 모르겠어요 ㅠ

---------------

입력예제1 에서,

1이 두 번 들어가기 때문에 그래프를 직접 그려본다면

1 - 2

X I

1 - 3 - 4 - 5

이런 그림이 되는게 맞나요? (막대가 간선입니다)

그럼 bfs로 탐색할 때 1에 대한 조건은 어떻게 판단되나요?ㅜㅜ

( 예를들면 탐색 순서에 있어서 2,3을 큐에 넣어서 진행한 다음 1에 대한 방문 여부를 확인할텐데 그 떄는

이미 방문했다는 판단을 하게되는지 아니면 새로 방문하게되는지... )

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

using namespace std;

vector<int> adj[100001];
int dist[501];

int n,m;
int cnt;

void bfs(){
	queue<int> q;
	q.push(1);
	dist[1] = 0;
	int cnt=0;
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(int nxt:adj[cur]){
			if(dist[nxt] || dist[cur]>2) continue;
			q.push(nxt);
			dist[nxt] = dist[cur]+1;
			cnt++;
		}
	}
	cout<<cnt;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	bfs();
	
}

tjdnfls1234 1년 전 0

15번 라인에서 출발점의 거리를 1로 주셨어요

eye3570 1년 전 0

dist 배열을 -1로 초기화하시면 됩니다.

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

문제

문제

출처

ICPC

[c++] 5567번 bfs로 접근(수정)

swo98 1년 전 0

tjdnfls1234 1년 전 0

eye3570 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말