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
'알고리즘' 카테고리의 다른 글
[swjungle 2기] 백준 1535 안녕 (0) | 2021.08.30 |
---|---|
[swjungle 2기] 그리디 알고리즘 (탐욕법) (0) | 2021.08.28 |
[swjungle 2기] 도둑! 배낭? Knapsack Problem(배낭문제, 냅색) (0) | 2021.08.27 |
[swjungle 2기]위상 정렬 알고리즘 (0) | 2021.08.23 |
[python] 함수 호출 방법 (0) | 2021.08.15 |
댓글