java-squid · 102092 · Apr 14, 2023 · Apr 2, 2023 · Apr 8, 2023 · Apr 9, 2023
diff --git a/08--graph/ragdoll/1325.py b/08--graph/ragdoll/1325.py
@@ -0,0 +1,44 @@
+import sys
+from collections import deque
+
+input = sys.stdin.readline
+
+vertex_count, edge_count = map(int, input().split())
+
+vertexes = [[] for _ in range(vertex_count + 1)]
+visit_count = [0] * (vertex_count + 1)
+
+for _ in range(edge_count):
+    from_vertex, to_vertex = map(int, input().split())
+    vertexes[from_vertex].append(to_vertex)
+
+
+def BFS(vertex: int):
+    deq = deque()
+    deq.append(vertex)
+
+    visited = [False] * (vertex_count + 1)  # 초기화 해야 방문 카운트를 계속 누적 가능
+
+    while deq:
+        vertex = deq.popleft()
+
+        for v in vertexes[vertex]:
+            if not visited[v]:
+                visited[v] = True
+                visit_count[v] += 1
+                deq.append(v)
+
+for vertex in range(1, vertex_count + 1):
+    BFS(vertex)
+
+maximum = 0
+for count in visit_count:
+    if maximum < count:
+        maximum = count
+
+for vertex in range(1, vertex_count + 1):
+    if visit_count[vertex] == maximum:
+        print(vertex, end=' ')
+
+# 가장 많이 방문된 vertex를 찾아야 함
+# 동점이 있는 경우 vertex 번호를 오름차순으로 출력
diff --git a/08--graph/ragdoll/1707.py b/08--graph/ragdoll/1707.py
@@ -0,0 +1,49 @@
+import sys
+sys.setrecursionlimit(10**6)
+input = sys.stdin.readline
+test_count = int(input())
+
+is_even = True
+
+
+def DFS(vertex: int):
+    global is_even
+    visited[vertex] = True
+
+    for v in vertexes[vertex]:
+        if not visited[v]:
+            groups[v] = (groups[vertex] + 1) % 2
+            DFS(v)
+        elif groups[vertex] == groups[v]:
+            is_even = False
+
+
+for _ in range(test_count):
+    vertex_count, edge_count = map(int, input().split())
+    vertexes = [[] for _ in range(vertex_count + 1)]
+    visited = [False] * (vertex_count + 1)
+    groups = [0] * (vertex_count + 1)
+    is_even = True
+
+    for i in range(edge_count):
+        from_vertex, to_vertex = map(int, input().split())
+        vertexes[from_vertex].append(to_vertex)
+        vertexes[to_vertex].append(from_vertex)
+
+    for i in range(1, vertex_count + 1):
+        if is_even:
+            DFS(i)
+        else:
+            break
+
+    if is_even:
+        print("YES")
+    else:
+        print("NO")
+
+# 혼자 힘으로 풀이 실패 함
+# 문제 내용 정리
+# 이분 그래프
+# => 서로 인접하지 않는 두 집합으로 그래프의 노드를 나눌 수 있다는 것
+# => 사이클이 발생하면 안된다고 함
+# => 탐색한 노드에 다시 접근했을 때 현재 노드의 집합과 같으면 안됨
diff --git a/08--graph/ragdoll/18352.py b/08--graph/ragdoll/18352.py
@@ -0,0 +1,37 @@
+import sys
+
+input = sys.stdin.readline
+
+vertex_count, edge_count, distance, begin_vertex = map(int, input().split())
+
+graph = [[] for _ in range(vertex_count + 1)]
+visited = [False] * (vertex_count + 1)
+for _ in range(edge_count):
+    from_vertex, to_vertex = map(int, input().split())
+    graph[from_vertex].append(to_vertex)
+
+answers = []
+
+
+def search(vertex: int, depth: int):
+    if depth > distance:
+        return
+
+    if depth == distance:
+        for v in graph[vertex]:
+            if not visited[v]:
+                visited[v] = True
+                answers.append(v)
+        return
+
+    for v in graph[vertex]:
+        search(v, depth + 1)
+
+
+search(begin_vertex, 1)
+
+if not answers:
+    answers.append(-1)
+
+for answer in answers:
+    print(answer)
diff --git a/08--graph/ragdoll/18352_sol.py b/08--graph/ragdoll/18352_sol.py
@@ -0,0 +1,37 @@
+import sys
+from collections import deque
+
+input = sys.stdin.readline
+
+vertex_count, edge_count, distance, begin_vertex = map(int, input().split())
+
+graph = [[] for _ in range(vertex_count + 1)]
+visited = [-1] * (vertex_count + 1)
+for _ in range(edge_count):
+    from_vertex, to_vertex = map(int, input().split())
+    graph[from_vertex].append(to_vertex)
+
+answers = []
+
+def BFS(vertex: int):
+    deq = deque()
+    deq.append(vertex)
+    visited[vertex] += 1
+    while deq:
+        current = deq.popleft()
+        for v in graph[current]:
+            if visited[v] == -1:
+                visited[v] = visited[current] + 1
+                deq.append(v)
+
+BFS(begin_vertex)
+
+for i in range(vertex_count + 1):
+    if visited[i] == distance:
+        answers.append(i)
+
+if not answers:
+    answers.append(-1)
+
+for answer in answers:
+    print(answer)