BFS 이용해서 풀었다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <string> #include <vector> #include <queue> using namespace std; bool visited[20001]; vector<int> link[20001]; struct _pair { int num; int cnt; }; queue<_pair> que; int maxCnt = 0; int solution(int n, vector<vector<int>> edge) { int answer = -1; int edgeN = edge.size(); for (int i = 0; i < edgeN; i++) { int a = edge[i][0]; int b = edge[i][1]; link[a].push_back(b); link[b].push_back(a); } visited[1] = true; que.push({ 1, 0 }); while (!que.empty()) { _pair pair = que.front(); que.pop(); if (pair.cnt > maxCnt) { maxCnt = pair.cnt; answer = 1; } else if (pair.cnt == maxCnt) { answer++; } for (int i = 0; i < link[pair.num].size(); i++) { int a = pair.num; int b = link[a][i]; if (visited[b]) continue; visited[b] = true; que.push({ b,pair.cnt + 1 }); } } return answer; } | cs |
'알고리즘' 카테고리의 다른 글
| 프로그래머스 (PROGRAMMERS) 문자열압축 (0) | 2021.01.18 |
|---|---|
| 프로그래머스 (Programmers) 입국심사 (0) | 2021.01.12 |
| 프로그래머스 (Programmers) 섬 연결하기 (0) | 2021.01.11 |
| 프로그래머스(programmers) N으로 표현 (0) | 2021.01.11 |
| [논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수 (0) | 2020.12.28 |
짬뽕얼큰하게
