https://www.acmicpc.net/problem/1325 if (!visited[nextNode]) { visited[nextNode] = true q.offer(nextNode) result[nextNode]++ } } } } val max = result.maxOrNull()!! val sb = StringBuilder() result.forEachIndexed { index, value -> if(value == max) sb.append(index).append(" ") } println(sb) } result는 각 컴퓨터가 해킹할 수 있는 컴퓨터 개수입니다. BFS를 한 번 진행할 때 마다 하나씩 증가시키고, 모든 노드(컴퓨터)에 대해 탐색을 진행합니다. 최종적으로, result 내 가..

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/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 난이도 : 골드 2 태그 : 데이크스트라, 그래프 이론 설명 다익스트라를 응용한 문제입니다. S에서 시작하여, G - H 혹은 H - G 구간을 거쳐, t1, t2, t3, 총 3개의 목적지 후보로 갈 수 있다 가정해보겠습니다. 이 때, 시작점인 S와 목적지인 T1의 최단거리가 S - G - H - T1 혹은 S - H - G - T1 과 같을 때, T1은 가능한 목적지 경로입니다. S - ..

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 난이도 : 골드 3 태그 : 수학, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 조합론, 백트래킹 설명 DFS를 사용해 풀면 되겠네! 라는 생각이 바로 떠올랐지만, 생각해보니 순수 DFS만으로 풀기에는 조금 무리가 있었습니다. 결국... 이게 뭐지??? 하는 생각에 태그를 펼쳐봤습니다. 그렇습니다. 이 문제는 1. 5 x 5 = 25명의 자리 중 7명을 뽑고(..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 데이크스트라 설명 한 도시에서 거리가 k인 도시를 찾는 문제입니다. 너비 우선 탐색을 사용하거나, 한 점에서 다른 모든 점까지의 최단거리를 구하는 다익스트라를 사용해도 될 것 같네요. 저는 너비 우선 탐색을 통해 풀이하였습니다. 소스코드 import ..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 데이크스트라 설명 다익스트라를 응용해야 하는 것은 쉽게 알아챌 수 있었지만, 상하좌우 탐색를 해야 하는 탐색에서 어떻게 구현하냐 고민을 많이 했습니다. 어음.. 다익스트라가 아니라 BFS를 사용해야 하나? 하는 마음에 질문게시판을 뒤적거려봤는데, 다익스트라 + BFS를 연상케 하는 형태로 풀 수 있었습니다 소스코드 import java...

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/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 다른 DFS/BFS 탐색과 비슷하지만, 대각선 탐색이 가능한 8방향 탐색입니다. 따라서 (1,0) (0,1) (-1,0) (0,-1) 상하좌우 방향에 이어 (1,1) (1,-1) (-1,1) (-1,-1) 대각선 4방향, 총 8개 방향입니다. 소스코드 import java.util.* val dx..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 이분 그래프 설명 https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 이분 그래프 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 2색변 이분 그래프의 예 그래프 이론에서 이분 그래프(二分graph,..