sh1mj1_log

https://sh1mj1-log.tistory.com/140 이전 글에서 계속 됩니다. 백준 1707 이분 그래프 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. 문제 분석 노드를 집합 2개로 나눌 때 인접한 노드끼리 같은 집합이 되면 안 됩니다. 즉, 같은 위 그림처럼 인접해있으면 색이 달라야 한다는 의미입니다. 만약 사이클이 발생한다면 이분 그래프가 불가능합니다. 이런 경우를 어떻게 알아낼 수 있을까요? 탐색 매커니즘에서 탐색한 노드..

그래프는 3가지 구현 방법이 있습니다. 에지 리스트, 인접행렬, 인접 리스트 로 구현할 수 있습니다. 에지 리스트(Edge list) 에지를 중심으로 그래프를 표현합니다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현합니다. 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현합니다. 가중치 없는 그래프를 에지 리스트로 표현 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분합니다. 1에서 2로 뻗어나가는 에지는 [1,2] 로 표현합니다. 이처럼 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 포현합니다. 노드를 배열에 저장하여 에지를 표현하므로 에지 리스트라고 합니다. 가중치 그래프를 에지 리스트로 표현 가중치..

이전 글 https://sh1mj1-log.tistory.com/136 에서 계속됩니다. 백준 1033 칵테일 https://www.acmicpc.net/problem/1033 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 1. 문제 분석 문제에서는 N-1 개의 비율로 N 개의 재료와 관련된 전체 비율을 알아낼 수 있다고 합니다. 그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있습니다. 그래서 임의의 노드에서 DFS 혹은 BFS 를 진행하면서 정답을 찾으면 됩니다. DFS 과정에서 유클리드 ..