Algorithm/Graph

[백준 1043번] 거짓말 (C++)

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 거짓말 문제는 그래프를 이용하여 해결할 수 있습니다. 파티에서 거짓말을 하려면 해당 파티에 오는 사람들은 모두 진실을 알지 못해야합니다. 진실을 아는 사람이 존재하지 않는다면, 모든 파티에서 과장을 할 수 있습니다. A는 진실을 아는 사람, B는 진실을 아는 사람과 같이 파티에 참석한 사람일 때, B가 참석한 파티에서도 거짓말을 할 수 없습니다. 먼저, B와 파티에서 거짓말을 한 경우, A와의 파티에서 진실..

[백준 2617번] 구슬 찾기 (C++)

https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 구슬 찾기 문제는 그래프로 해결할 수 있습니다. 무게가 중앙값이 될 수 없는 구슬을 찾는 문제입니다. 따라서, 무게가 중앙값인 구슬은 본인보다 가벼운 구슬이 (n - 1) / 2개, 무거운 구슬이 (n - 1) / 2개 있어야 합니다. 따라서, 가벼운 구슬이 (n - 1) / 2개보다 많거나, 무거운 구슬이 (n - 1) / 2개보다 많은 구슬은 무게가 중앙값이 될 수 없습니다..

[백준 1707번] 이분 그래프 (C++)

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 다음과 같은 조건을 만족시키는 집합의 분할을 가질 수 있다면, K분 그래프라고 합니다. 위키백과 인접한 두 정점은 서로 다른 정점 집합에 속한다. k = 2일 때, 이를 이분 그래프라고 합니다. 따라서 인접한 정점의 색이 서로 다르도록 색을 칠해주어야 하고, 색의 수는 2가 되어야 합니다. 따라서, BFS를 이용하여 각 정점에 색을 부여하되, 이미 방문한 정점의 색이 인접한 정점과 색이 같으면 이..