https://programmers.co.kr/learn/courses/30/lessons/49189
코딩테스트 연습 - 가장 먼 노드
6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3
programmers.co.kr
그래프 유형이라지만 문제 풀 때는 bfs개념을 섞어서 풀었다.
먼저 각 노드의 인접 리스트를 생성한 후, 1번 노드에 근접한 노드부터 방문해 체크하고 큐에 삽입한다.
한 번 체크된 노드는 큐에 삽입하지 않는다.
거리 비교는 level 변수를 이용해 이전보다 더 긴 거리이면 갯수를 초기화하고 같으면 1을 추가한다.
(혼자 풀었다 뿌듯...)
소스코드
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int n, vector<vector<int>> edge) {
int answer = 0;
//인접리스트와 체크 배열, 큐 생성
vector<vector<int>> v(n+1);
vector<int> ch(n+1,-1);
queue<pair<int,int>> q;
int a, b;
//인접리스트 채우기 , 무방향이므로 양 노드 모두에 삽입
for(vector<int> i : edge) {
a = i[0];
b = i[1];
v[b].push_back(a);
v[a].push_back(b);
}
//현재 떨어진 레벨 저장할 변수
int level = -1;
//거리가 0인 1번 노드부터 큐에 삽입
pair<int, int> p;
ch[1] = 0;
q.push(make_pair(1,0));
//큐가 빌 때 까지 실행
while(!q.empty()) {
p = q.front();
q.pop();
a = p.first;
b = p.second;
//이전 레벨과 다르다면 카운트 수 초기화
if(level != b) {
level = b;
answer = 1;
}
else answer++;
//돌면서 인접 노드에 방문했는지 확인
for(int i : v[a]) {
//방문 했으면 패스
if(ch[i] != -1) continue;
//방문 안 했으면 방문 체크하고 큐에 삽입
ch[i] = b+1;
q.push(make_pair(i,ch[i]));
}
}
return answer;
}
'CodingTest Practice > Programmers' 카테고리의 다른 글
프로그래머스 : SUM,MAX,MIN (SQL, ORACLE) (0) | 2022.06.06 |
---|---|
프로그래머스 : SELECT (SQL , ORACLE) (0) | 2022.06.06 |
프로그래머스 : 프린터 (C++, Lv.2, 큐) (0) | 2022.05.31 |
프로그래머스 : 여행경로 (C++, Lv.3, DFS) (1) | 2022.05.27 |
프로그래머스 : 단어변환(C++, Lv.3, BFS) (0) | 2022.05.27 |