코딩고치

1. 문제 주소: https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이 www.acmicpc.net 문제 유형: 해시, 집합, 그래프 풀이 가정: 'A'와 'B'가 친구이고 'B'와 'C'가 친구일 때 'B'와 'C'의 친구 네트워크 내의 사람 수는 3명이다. 'A'를 'B'의 parent node로 두고 'B'를 'C'의 parent node로 둔 다음에 두 parent node를 이어준다. 이것을 이용하여 코드를 작성하였다. 1. 두 사람을 입력받았을 때 parent_node에 두..

최단 경로 알고리즘 최단 경로 문제 두 노드를 잇는 최단 경로 찾는 문제 가중치 그래프에서 가중치 합이 최소가 되는 것을 찾는 문제 문제 종류 단일 출발 및 단일 도착 문제 특정 노드 2개를 선택 후 가장 짧은 경로를 찾는 문제 단일 출발 문제 특정 노드 1개에서 다른 노드들 간 가장 짧은 경로를 찾는 문제 전체 쌍 문제 그래프 내 노드 쌍에 대한 최단 경로를 찾는 문제 다익스트라 알고리즘 단일 출발에 대한 답을 찾는 문제 첫 노드를 기준으로 인접한 노드를 추가해 가면서 최단 거리를 구해나가는 방법 너비 우선 탐색과 유사 우선순위 큐를 이용 1) 첫 노드를 기준으로 각 노드들 간의 거리를 저장하는 배열 생성 첫 노드의 거리는 0, 나머지는 무한대로 설정 (inf) 첫 정점 거리 (0)을 먼저 배열에 입력..

그래프 (Graph) 실제 세계의 현상이나 사물을 정점 (Vertex) 또는 노드 (Node)와 간선 (Edge)로 표현하기 위해 사용한다. 관련 용어 노드 (Node): 위치를 알려준다. 정점 (Vertex)라고도 한다. 간선 (Edge): 노드를 연결한 선이다 (link 또는 branch라고 한다). 위치 관계를 표시 인접 정점 (Adjacent Vertex): 간선으로 직접 연결된 노드 참고 용어 정점의 차수 (Degree): 무방향 그래프에서 하나의 노드에 인접한 노드의 수 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 (Path Length): 경로를 구성하는 간선의 수 단순 경로..