🌽 문제
🥔 풀이
BFS 기본 수준 활용 문제이다.
냅다 DFS로 박았다가 빠꾸하고 마음의 평화를 찾았다.
DFS는 어떤 순서로든 방문할 수 있어 거리 계산을 일일이 관리해야 하고,
최단 거리인지 보장하기 어렵다.
BFS는 항상 레벨 순으로 탐색하는 최단 거리 탐색에 최적화된 알고리즘이다.
가장 먼 노드 = 최단 거리 기준 가장 큰 값을 구하는 것이므로 BFS로 풀어내자.
먼저, 엣지를 갖다가 양방향 그래프로 가공해준다.
1번 노드와의 거리를 저장하는 벡터를 생성하고 -1로 초기화한다.
고담에 BFS로 들어가자.
출발 노드인 1번 노드의 거리를 0으로 갱신하고,
차례로 탐색할 queue에 담아주면서 while문 입장.
queue 앞머리를 현재 탐색 노드로 저장하고, pop 한다.
현재 탐색 노드에서 갈 수 있는 노드를 돌며 거리가 갱신된 적 없다면(-1)
현재 노드 + 1로 갱신하는 동시에 queue에 넣어주기를
queue가 비기 전까지 반복한다.
갱신된 dist의 최댓값을 찾고,
그 값과 같은 경우 count하여 return하면 끋
*max_element랑 count_if는 첨 써봤는데 아주 편리하다.
간단한 사용법을 정리해보자.
max_element (min_element)
#include <algorithm> 여기 들어있다.
-
max_element(start, end)
: 범위 내 최대값의 iterator 반환 -
*max_element(start, end)
: 범위 내 최대값의 value 반환 -
min_element(start, end)
: 범위 내 최소값의 iterator 반환 -
*min_element(start, end)
: 범위 내 최소값의 value 반환
count_if (count)
마찬가지로 #include <algorithm> 여기 들어있다.
-
count(start, end, value)
: 범위 내 value와 일치하는 값의 개수 반환 -
count_if(start, end, 조건(return bool))
: 범위 내 조건에 맞는 값의 개수 반환
이 때 조건문은 람다 함수 구조 []() {};를 갖는다.
[]: 람다 내부에서 외부 변수에 접근할지 여부를 명시한다.
[]외부 변수 캡처하지 않음[x]외부 변수 x를 값으로 복사[&x]외부 변수 x를 참조로 캡처[=]외부 모든 변수를 값으로 복사[&]외부 모든 변수를 참조로 캡처[=, &x]기본은 값, x만 참조
(): 매개변수 리스트로, 함수처럼 인자를 받을 수 있다.
🥬 코드
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int solution(int n, vector<vector<int>> edge) {
vector<vector<int>> graph(n + 1);
vector<int> dist(n + 1, -1);
queue<int> q;
for (auto e : edge) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
q.push(1);
dist[1] = 0;
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int next : graph[curr]) {
if (dist[next] == -1) {
dist[next] = dist[curr] + 1;
q.push(next);
}
}
}
int maxDist = *max_element(dist.begin(), dist.end());
int cnt = count_if(dist.begin(), dist.end(), [maxDist](int d) {
return d == maxDist;
});
return cnt;
}🥜 채점
