Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 로드밸런서
- Apache Kafka
- 쿠버네티스
- 월미도
- 오일러프로젝트
- 알고리즘
- Spring
- springboot
- 인천여행
- 백트래킹
- DFS
- VPC
- 클라우드 컴퓨팅
- 코드업
- aws
- 프로그래밍문제
- Spring Data JPA
- 자료구조
- 클라우드
- Docker
- 스프링 부트
- 백준
- Elasticsearch
- JPA
- 스프링부트
- Spring Boot
- 카프카
- 스프링
- Kafka
- gcp
Archives
- Today
- Total
GW LABS
[Backjoon] 촌수계산 본문
한동안 그래프 탐색 문제를 다뤄보지 않아서 복습겸, C++ 공부겸 기본적인 DFS 문제를 풀어봤다. 백준 2644번 촌수계산 문제는 인접 리스트 형태의 자료구조에서 DFS를 통해서 노드의 연결 깊이를 계산하는 문제였다. 인접 리스트이기 때문에 vector를 사용해서 풀었는데 파이썬 보다는 코드가 길어지는 경향이 있다. 아래는 소스코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int search(int searchStart, int searchEnd, vector<vector<int>> graph, bool visited[101], int count) {
if (searchStart == searchEnd) return count;
int answer = -1;
visited[searchStart] = true;
for (int i = 0; i < graph.at(searchStart).size(); ++i) {
if (!visited[graph.at(searchStart).at(i)]) {
answer = max(search(graph.at(searchStart).at(i), searchEnd, graph, visited, count+1), answer);
}
}
return answer;
}
int main() {
bool visited[101] = {false};
vector<vector<int>> graph;
int famliyCount;
cin >> famliyCount;
int searchStart, searchEnd;
cin >> searchStart >> searchEnd;
int nodeCount;
cin >> nodeCount;
for (int i = 0; i <= famliyCount; ++i) {
vector<int> temp;
graph.push_back(temp);
}
for (int i = 0; i < nodeCount; ++i) {
int nodeStart, nodeEnd;
cin >> nodeStart >> nodeEnd;
graph.at(nodeStart).push_back(nodeEnd);
graph.at(nodeEnd).push_back(nodeStart);
}
int answer = search(searchStart, searchEnd, graph, visited, 0);
cout << answer << endl;
return 0;
}
'Algorithm & DataStructure' 카테고리의 다른 글
[Backjoon] 숫자놀이 (0) | 2022.02.08 |
---|---|
[Backjoon] 소수&팰린드롬 (0) | 2021.01.12 |
[Backjoon] 트럭 주차 (0) | 2021.01.02 |
[Backjoon] 회전하는 큐 (0) | 2020.12.18 |
[Backjoon] 통나무 건너뛰기 (0) | 2020.12.13 |