본문 바로가기
알고리즘

[swjungle 2기] 백준 2617 구슬 찾기

by KBS 2021. 8. 24.
728x90

백준 2617 구슬 찾기(dfs)

  • dfs로 풀이하였고 특정 구슬보다 높은 구슬의 배열과 낮은 구슬의 배열 2개를 만들어서 갯수를 구해줘었습니다.

  • 특정 구슬보다 높은 구슬의 갯수 또는 낮은 구슬의 갯수가 mid = (n+1)//2 이상이면 중간 무게의 구슬이 될수 없어 정답에 추가해 주었습니다.

  • 의문점은 높은 구슬의 갯수와 낮은 구슬의 갯수가 모두 mid보다 높은 가능성이 있었나? 였습니다.

    import sys
    
    n, m = map(int, sys.stdin.readline().split())
    
    low = [[] for _ in range(n + 1)]
    high = [[] for _ in range(n + 1)]
    for i in range(m):
        x, y = map(int, sys.stdin.readline().split())
        high[y].append(x)
        low[x].append(y)
    
    mid = (n + 1)//2
    answer = 0
    
    def dfs(v, map, visited):
        visited[v] = True
        for i in map[v]:
            if not visited[i]:
                dfs(i, map, visited)
    
    for i in range(1, n+1):
        lowNum = 0
        highNum = 0
        lowVisited = [False] * (n+1)
        highVisited = [False] * (n+1)
        lowCheck = dfs(i, low, lowVisited)
        highCheck = dfs(i, high, highVisited)
    
        for j in range(n+1):
            if lowVisited[j] == True:
                lowNum += 1
            if highVisited[j] == True:
                highNum += 1
        if (lowNum-1) >= mid or (highNum-1) >= mid:
            answer += 1
    print(answer)
728x90

댓글