230309 - 그래프

[robert-min]

문제

1. boj11403 - 경로 찾기 링크
2. boj5567 - 결혼식 링크
3. boj1389 - 케빈 베이컨의 6단계 법칙 링크
4. boj1707 - 이분 그래프 링크
5. boj1043 - 거짓말 링크

[robert-min]

boj11403 - 경로 찾기

"""
Return : 모든 정점에 양수인 경로가 있는지 출력
- 경로가 있는 경우 1

graph 그리기
모든 노드 탐색 -> 갈 수 있으면 visited[1]
"""
import sys
input = sys.stdin.readline

N = int(input())

graph = [[] for _ in range(N)]
for i in range(N):
    row = list(map(int, input().split()))
    for j, r in enumerate(row):
        if r == 1:
            graph[i].append(j)
# print(graph)

def dfs(now):
    for nx in graph[now]:
        if not visited[nx]:
            visited[nx] = 1
            dfs(nx)

for i in range(N):
    visited = [0] * N
    dfs(i)
    print(*visited)

[robert-min]

boj5567 - 결혼식

"""
Return : 결혼식에 초대할 사람의 수
- 상근이 친구, 친구의 친구까지 초대, depth == 2 break
- 상근 = 1

- 이미 초대한 친구는 탐색X
"""
import sys
input = sys.stdin.readline

N = int(input())
M = int(input())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [0] * (N+1)
visited[1] = 1

def dfs(now, depth):
    if depth == 2:
        return
    else:
        for nx in graph[now]:
            visited[nx] = 1
            dfs(nx, depth + 1)

dfs(1, 0)
print(visited.count(1)-1)

[robert-min]

boj1389 - 케빈 베이컨의 6단계 법칙

"""
Return : 케빈 베이컨 수가 가장 작은 사람 번호 출력(여러명일 경우 가장 작은 수)

- 본인 기준 다음 노드까지 몇 개의 노드를 방문해야하는지 합
- depth 합 계산
- 최소 값 갱신
"""
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# def dfs(now, depth):
#     global cnt
#     for nx in graph[now]:
#         if not visited[nx]:
#             cnt += depth
#             visited[nx] = 1
#             dfs(nx, depth+1)

from collections import deque
def bfs(now):
    global cnt
    Q = deque([(now, 1)])
    while Q:
        now, depth = Q.popleft()
        for nx in graph[now]:
            if not visited[nx]:
                cnt += depth
                visited[nx] = 1
                Q.append((nx, depth + 1))

# 모든 노드 탐색
min_cnt = sys.maxsize
answer = 0
for i in range(1, N+1):
    cnt = 0
    visited = [0] * (N+1)
    visited[i] = 1
    # dfs(i, 1)
    bfs(i)
    if cnt < min_cnt:
        min_cnt = cnt
        answer = i
print(answer)

[robert-min]

boj1707 - 이분 그래프

"""
Return : 이분 그래프 YES, 아니면 NO

- visited = 0, 1, 2
- 방문하지 않았으면 1 or 2
- 방문했던 노드인데 같은 색이면 break
"""
import sys
input = sys.stdin.readline

from collections import deque
def bfs(start):
    Q = deque([(start, 2)])
    visited[1] = 1
    while Q:
        now, color = Q.popleft()
        for nx in graph[now]:
            if not visited[nx]:
                visited[nx] = color
                if color == 1:
                    Q.append((nx, 2))
                else:
                    Q.append((nx, 1))
            else:
                if visited[nx] == visited[now]:
                    return False
    return True

for _ in range(int(input())):
    V, E = map(int, input().split())
    graph = [[] for _ in range(V+1)]
    for _ in range(E):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    # 탐색
    visited = [0] * (V+1)
    flag = True
    for i in range(1, V):
        if not visited[i]:
            if not bfs(i):
                flag = False
                break

    if flag:
        print("YES")
    else:
        print("NO")

[robert-min]

boj1043 - 거짓말

"""
Return : 과장된 이야기를 할 수 있는 파티의 개수
- 진실을 아는 사람과 같이 있는 파티에서는 과장된X

- people = [T, F] 진실을 아는 사람 체크
- 하나라도 연결되어 있으면 거짓X
- 그래프
"""
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
input_known = list(map(int, input().split()))
known = set(input_known[1:])
parent = [i for i in range(N+1)]

def find(x):
    if parent[x] != x:
        return find(parent[x])
    return x

def union(a, b):
    a = find(a)
    b = find(b)

    if a in known and b in known:
        return

    # 사실을 아는 사람과 union 시 해당 사람이 부모가 되도록
    if a in known:
        parent[b] = a
    elif b in known:
        parent[a] = b
    else:
        if a < b:
            parent[b] = a
        else:
            parent[a] = b

parties = []
for i in range(M):
    input_party = list(map(int, input().split()))
    party_len = input_party[0]
    party = input_party[1:]

    for i in range(party_len - 1):
        union(party[i], party[i+1])
    parties.append(party)

# print(parent)
# print(parties)

def check(party):
    for i in party:
        if find(parent[i]) in known:
            return False
    return True

ans = 0
for party in parties:
    if check(party):
        ans += 1

print(ans)