플로이드-워셜 검색 결과
2 개의 검색 결과가 있습니다.
개발/알고리즘

[백준 2224] 명제 증명 (python)

2224번: 명제 증명 첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전건 순으로 정렬하고, 전건이 같은 경우에는 후건 순으 www.acmicpc.net 플로이드-워셜 알고리즘을 사용한다. A -> B, B -> C 일 때, A-> C인가를 확인하는 문제에서 자주 사용된다. A(65)를 0, z(122)를 57로 인덱스를 만들어주는 배열 arr를 생성한다. 전, 후가 같은 문자와 같은 명제들은 무시하고 배열에 저장한다. 플로이드-워셜을 사용하여 서로 연결해준다. 연결고리 개수를 출력하고 알파벳 순으로 답을 출력한다. import sys input = sys.stdin.readline N = int(input()) ..

2021. 7. 12. 23:23
개발/알고리즘

[백준 2458] 키 순서 (python)

2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 플로이드 워셜을 이용하자! arr[i][j]는 i키 < j키라면 1을 넣어준다. i키 < k키 , k키 < j키 라면 i키 < j키 이므로 플로이드 워셜을 통해 arr를 업데이트 해준다. arr[i][j] 또는 arr[j][i]가 1이라면 i와 j의 대소관계를 파악할 수 있다. 대소관계를 파악할 수 있는 사람의 수를 세어 본인을 제외한 나머지(N-1)라면 카운트 해준다. import sys input = sys.stdin.readline N, M = map(int..

2021. 5. 4. 18:34