99클럽 코테 스터디 17일차 TIL, 백준 / 사자와 토끼 / 17834

🔑 오늘의 학습 키워드 : 이분그래프

🔗 문제링크 https://www.acmicpc.net/problem/17834

 

import sys
from collections import deque

input = sys.stdin.readline

# 이분 그래프인지 아닌지 판별하는 함수
# 각각의 그룹도 같이 return
def is_bipartite(n,graph):
    color = [None] * (n+1)
    
    def bfs(start):
        queue = deque([start])
        color[start] = True
        while queue:
            node = queue.popleft()
            for near in graph[node]:
                if color[near] == None:
                    color[near] = not color[node]
                    queue.append(near)
                # 갱신된 값이 이전 값이랑 같으면 이분 그래프가 아님
                elif color[near] == color[node]:
                    return False
        return True
    
    for i in range (1,n+1):
        if color[i] == None:
            if not bfs(i):
                return False, [] ,[]
    
    true_group,false_group = [],[]
    
    for i in range (n):
        if color[i]:true_group.append(i)
        else : false_group.append(i)
            
    return True, true_group,false_group

def count_unending_positions(n, graph):
    bipartite, true_group, false_group = is_bipartite(n,graph)
    if not bipartite :
        return 0
    return len(true_group) * len(false_group) * 2

n, m = map(int, input().split())
bushes = [tuple(map(int, input().split())) for _ in range(m)]
graph = {i: [] for i in range(1, n + 1)}
for u, v in bushes:
    graph[u].append(v)
    graph[v].append(u)
    
print(count_unending_positions(n, graph))

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

이분 그래프라는 개념을 몰랐기 때문에 그냥 수학적으로 접근했었다.

 

당장 옆에 있으면 만나지 않는 경우가 되고, 2의 배수만큼 떨어질 때도 만나지 않는 경우가 된다고 생각했다.

 

노드의 개수가 홀수면 만날 수 있기 때문에 0을 return하고

 

노드의 개수가 짝수면 N ^ 2 // 2 를 하면 될 줄 알았다. 하지만 역시나 골드 1을 달랐다..

 

문제 알고리즘 유형을 보고 이분 그래프 알고리즘을 알게 되었고 이를 활용해서 풀어야겠다고 생각했다.

 

⏰ 예상 시간 복잡도 O(N * M )

제한 사항

첫 번째 줄에 수풀의 수 N(2 ≤ N ≤ 50,000)과 오솔길의 수 M(1 ≤ M ≤ 500,000)이 공백으로 구분되어 주어진다.

😎 알고리즘 개요

코드를 작성하기 전에 3가지로 나눴다.

 

1. 입력 부분

n, m = map(int, input().split())
bushes = [tuple(map(int, input().split())) for _ in range(m)]
graph = {i: [] for i in range(1, n + 1)}
for u, v in bushes:
    graph[u].append(v)
    graph[v].append(u)

양방향 그래프 형태로 바꿔 주었다.

2. 이분 그래프인지 판별하는 로직 부분

# 이분 그래프인지 아닌지 판별하는 함수
# 각각의 그룹도 같이 return
def is_bipartite(n,graph):
    color = [None] * (n+1)
    
    def bfs(start):
        queue = deque([start])
        color[start] = True
        while queue:
            node = queue.popleft()
            for near in graph[node]:
                if color[near] == None:
                    color[near] = not color[node]
                    queue.append(near)
                # 갱신된 값이 이전 값이랑 같으면 이분 그래프가 아님
                elif color[near] == color[node]:
                    return False
        return True
    
    for i in range (1,n+1):
        if color[i] == None:
            if not bfs(i):
                return False, [] ,[]
    
    true_group,false_group = [],[]
    
    for i in range (n):
        if color[i]:true_group.append(i)
        else : false_group.append(i)
            
    return True, true_group,false_group

 

bfs를 돌면서 현재 노드와 그 근처 노드의 부호를 다르게 바꿔가며 갱신해나갔다

 

1 - 2 - 3 이렇게 되었으면 True - False - True 이런식으로 갱신을 해나가는데

 

이때 이전에 갱신이 된 경우에 다시 밟을 때 전과 같으면 이분 그래프가 아니므로 False를 return한다.

 

그렇게 싸이클이 여러개가 있을 수 있기 때문에 모든 노드들에 대해 bfs를 적용해준다.

 

그 후 정답을 위해서 이 그래프가 이분 그래프를 만족하는지 여부와, true인 그룹과 false인 그룹을 나누어서 return해준다

3. 출력 부분

def count_unending_positions(n, graph):
    bipartite, true_group, false_group = is_bipartite(n,graph)
    if not bipartite :
        return 0
    return len(true_group) * len(false_group) * 2

 

2번에서 나온 결과를 가지고 출력을 해준다.

 

이때 토끼가 가능한 부분을 true_group, 사자가 가능한 부분을 false_group이라고 하면

 

각각 그룹에서 선택되는 경우 nC1 * nC1와 토끼가 false, 사자가 true인 경우 2가지를 해서 return을 해준다.

 

✅ 오늘의 회고

- 이분 그래프에 대해 알 수 있었다.

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL