백준 15723번 풀이(python)

링크 : https://www.acmicpc.net/problem/15723


dfs와 비슷한 느낌의 재귀함수로 충분히 풀이 가능한 문제였다. T가 나오면 바로 종료해버렸다.

#not floyd warshall algorithm
#my solve : dfs
bef = []
n=int(input())
for i in range(n):
    x, mid, y = input().split(" ")
    bef.append([x, y])
    
def dfs(first, height, last):
    global bef, n
    height -= 1
    for i in range(len(bef)):
        if bef[i][0] == first:
            if height >= 1:
                if last != bef[i][1]:
                    if dfs(bef[i][1], height, last) == True:
                        return True
                else:
                    print("T")
                    return True
            elif height == 0:
                if last != bef[i][1]:
                    pass
                else:
                    print("T")
                    return True
    if height == n-1:
        print("F")
        
for j in range(int(input())):
    x, mid, y = input().split(" ")
    dfs(x, n, y)

하지만 이 문제의 다른 풀이가 있다고 하는데, 그것 때문에 이 문제가 gold5(solved.ac 난이도 측정 기준) 수준이라고 한다.

<플로이드 와샬> 알고리즘으로 풀 수 있다고 한다.