[백준] 14236 명제 증명, python

https://www.acmicpc.net/problem/14236

 

 

처음에는 모든 명제가 함축되기 위해선 i=> j명제들의 i와 j가 모두 2회 이상씩 나와야 함축된다고 생각했다.

예를 들면 1=>2와 2=>1처럼 1과 2가 2회 이상 나와야 함축이라고 생각해서 백트래킹으로 dfs를 돌면서 명제가 2번씩 등장하는 케이스들을 모두 찾은 다음, 해당하는 케이스에서 bfs를 돌면서 한 i에서 모든 j로 가는 경로가 있으면 통과라고 풀었는데 시간초과가 나서 해결하지 못하였다.

이 문제는 SCC를 구하는 문제이다.

 

 

 

강한 연결 요소(SCC), 코사라주(Kosaraju) 알고리즘, python

강한 연결 요소(SCC), 코사라주(Kosaraju) 알고리즘, python

 

 

 

 

모든 명제를 함축한다는것은 u=> v와 v=> u가 모두 존재한다는 것이고, 따라서 명제를 몇 개 고르고 그 명제들이 SCC인 경우에 대해 가장 어려운 난이도와 가장 쉬운 난이도의 차이의 최솟값, 즉 난이도가 최대한 균등한 경우를 구하면 된다.

 

또한 여기서 명제를 고르는 케이스를 combinations을 사용하게 되면 n=50이라 매우 커지게 된다.

따라서 모든 명제를 난이도 순으로 정렬해서 양 끝에서 투포인터로 제거해 나가면서 SSC인지 여부를 판별하고, 난이도 차이의 최솟값을 갱신하면 된다.

 

 

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]


edges = []
# 모든 명제들을 배열에 저장후 난이도 기준으로 정렬
for i in range(n):
    for j in range(n):
        if i!=j:
            edges.append((arr[i][j], i, j))

edges.sort()


def dfs(graph, node, visited):
    visited[node] = True
    for next in graph[node]:
        if not visited[next]:
            dfs(graph, next, visited)

# SSC여부를 판별하는 함수(코사라주 알고리즘)
def valid(L, R):
    graph = [[] for _ in range(n)]
    rev = [[] for _ in range(n)]

    for w,x,y in edges[L:R+1]:
        graph[x].append(y)
        rev[y].append(x)

    visited = [False]*n
    dfs(graph, 0, visited)
    if not all(visited): return False

    visited = [False]*n
    dfs(rev, 0, visited)
    if not all(visited): return False

    return True


# 정렬된 명제들을 투포인터로 최솟값 계산
answer = float('inf')
L = 0 
for R in range(len(edges)):
    while L<=R and valid(L,R):
        answer = min(answer, edges[R][0]-edges[L][0])
        L += 1

print(answer if answer != float('inf') else 0)