일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 양자우위
- 파이썬
- 얽힘상태
- 머신러닝
- 양자역학
- 트리
- Lv3
- 검증 데이터
- Top Tab Navigator
- 머신러닝 교재
- 다중분류
- 빅테크 이슈
- 알고리즘
- 줄 서는 방법
- 아마존의 반독점 역설
- 리나칸
- 다중큐빗
- 나의 첫 머신러닝/딥러닝
- Bottom Tab Navigator
- Amazon's Antitrust Paradox
- 전자중첩
- qubit
- NISQ
- 프로그래머스
- 이진분류
- 단일큐빗
- 트리의지름
- 머신러닝 검증
- 플랫폼 독점
- 다중 레이블 분류
Archives
- Today
- Total
엄지척 블로그
[프로그래머스 - 순위] [그래프][DFS] 본문
https://programmers.co.kr/learn/courses/30/lessons/49191
해당 문제에 대한 풀이를 검색한 결과
플로이드 와샬 알고리즘을 활용한 풀이가 많았지만,
실전에서 과연 플로이드 와샬 알고리즘을 활용할수있을까? 라는 의문이 더 앞선 문제였다.
그래서 조금은 흔한 방법인 DFS 를 활용한 풀이를 게시할려 한다.
풀이방법
1. 권투 대회에서 이기는 방향, 지는 방향으로 Dictionary 배열 생성 총 두개를 생성한다.
권투에서 이기는 방향으로 화살표로 표현했을시
다음과 같이 Dictionary 두개를 생성할수있다.
Dict = { 1:[2] , 3:[2] ,4:[2],2:[5] }
Dict = { 2:[1,3,4] , 5:[2] }
2. 1~n 까지 돌면서 이기는 방향 , 지는 방향으로 dfs 탐색을 하며 visit 배열 체크를 한다.
3. 1~n 까지 visit 배열의 합이 n 일시 answer 값에다가 +1 을 해준다.
visit = [0] * 200
def get_dfs(now, node_dict):
global visit
visit[now] = 1
for val in node_dict[now]:
if visit[val] != 1:
get_dfs(val, node_dict)
def solution(n, results):
global visit
answer = 0
front_dict = {}
back_dict = {}
for i in range(1, n+1):
front_dict[i] = []
back_dict[i] = []
for result in results:
front_dict[result[0]].append(result[1])
back_dict[result[1]].append(result[0])
for i in range(1, n+1):
visit = [0] * 200
get_dfs(i, front_dict)
get_dfs(i, back_dict)
if sum(visit) == n:
answer += 1
return answer
print(solution(5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]))
'Algorithm' 카테고리의 다른 글
[프로그래머스][줄 서는 방법] (0) | 2023.01.15 |
---|---|
(백준 1967번) 트리의 지름 증명 (2) | 2020.12.20 |
Comments