https://www.acmicpc.net/problem/17270 17270번: 연예인은 힘들어 첫 번째 줄에는 약속 장소 후보의 수 V와 약속 장소를 연결하는 총 길의 수 M이 주어진다. (2 ≤ V ≤ 100, 1 ≤ M ≤ 1,000) 그리고 다음 M개의 각 줄에는 a, b, c 가 주어진다. a, b는 길의 시작과 끝이 www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 데이크스트라, 플로이드–워셜 설명 다익스트라 혹은 플로이드 워셜을 응용해 풀 수 있는 문제입니다. 계속 틀렸습니다를 받아서 질문게시판을 들여다봤는데, 아니나 다를까 지문이 불친절하다는 의견이 잔뜩 있었습니다... 질문게시판들을 둘러보며 지문을 몇 번이고 다시 읽어봤는데, 해당 조건을 하나씩 적용하면서 ..

https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 줄에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 이론, 자료 구조, 그래프 탐색, 분리 집합, 플로이드–워셜 설명 다소 복잡한 문제라, 지문을 두 세번 정도 정독했던 것 같네요. 서로 알고 있는 사람들의 관계가 주어질 때, 서로 알고 있을 경우 무조건 같은 위원회지만, 위원회는 최대한 많아야 하므로, 서로 알고 있지 않을 경우 무조건 다른 위원회로 분리합니다. 위의 말은 최댓값이... 최소가 된다...?는 ..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 플로이드-워셜 설명 플로이드 워셜 알고리즘을 응용하여 풀 수 있을 것 같습니다. 플로이드 워셜 알고리즘을 잘 모르겠다면, 아래 포스팅을 참고해주세요. https://uknowblog.tistory.com/39 [백준 11404번][Kotlin] 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 플로이드 워셜 설명 https://uknowblog.tistory.com/168 [백준 10159번] [Kotlin] 저울 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, ..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 그래프 탐색, 플로이드워셜 설명 각 물건들의 비교결과가 주어질 때, 각 물건과 비교결과를 알 수 없는 물건의 개수를 출력해야 합니다. 저는 처음에, 특정 값에 따른 비교가 아니라, 두 물건간의 우열이 주어진 상태라는 것만 보고, 위상정렬을 떠올려 바로 위상정렬로 풀이를 진행하려 했으나, 비교결과를 알 수 없는 물건의 개수를 출력하..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 데이크스트라, 플로이드-워셜 설명 각 정점에서 m 만큼의 비용 안에 갈 수 있는 정점들의 아이템 값의 최대값을 구하는 문제입니다. 한 정점과 연결된 다른 정점을 순차적으로 탐색하는 방식으로 DFS, 다익스트라 알고리즘을 사용해 풀이할 수도 있지만, 본 포스팅에서는 플로이드 - 워셜 알고리즘을 사용하여 풀이하겠습니다. 소스코드 인풋값 세팅 val MAX_VALU..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프이론, 플로이드 - 워셜 설명 문제의 제목처럼 플로이드 - 워셜 알고리즘을 이용해 해결할 수 있는 문제입니다. 플로이드 - 워셜 알고리즘의 기본격인 문제이니, 해당 알고리즘을 알고 계신다면 어렵지 않게 풀 수 있습니다. 저는 잘 몰라서 플로이드 - 워셜 알고리즘이 뭔지 찾아보고서야 풀었네요...ㅎㅎ 소스코드 값 입력과 테이블 준비 val br = BufferedR..