GW LABS

쉬운 그래프 문제 중 하나였다. 기본적인 개념을 복습하기 좋게 문제가 설계되어 있었다. 방향 그래프에 대한 개념과 그래프 순회방법을 복습했다. 해당 문제는 인접리스트를 쓸 필요가 없는데 인접 노드가 하나로 고정되어 있기 때문이다. 아래는 소스코드이다. #include #include #include using namespace std; int graph[1001]; bool visited[1001]; void bfs(int start) { queue q; q.push(graph[start]); visited[start] = true; while (!q.empty()) { int now = q.front(); q.pop(); if (!visited[now]) { visited[now] = true; q.p..

C++로 그래프 탐색에 대한 문제를 연습한 적이 많지 않다. 파이썬으로 풀때와 차이점은 BFS 문제에 그래프 깊이 정보를 pair 형식으로 queue에 넣어도 메모리 초과 문제가 발생하지 않는 것 같다(오....). 1389번 케빈 베이컨의 6단계 법칙은 양방향 인접리스트를 입력받아 그래프 노드간 거리를 구하고, 그 합계가 최소인 지점을 찾는 문제이다. DFS로 풀이하려고 했는데 문제 분류에 BFS가 되어 있어 BFS로 풀이했다. #include #include #include #include #include using namespace std; bool visited[201] = {false}; int getLinkScore(int user, int target, map link) { int score..