https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 난이도 : 골드 1 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 최소 스패닝 트리 설명 DFS / BFS를 사용해 각 섬을 그룹화 해줍니다. 그리고 각 섬의 모든 점들을 저장해 놨다가, 상하좌우로 방향으로 다리를 만들 수 있는지 확인합니다. 상하좌우 방향으로 현재의 섬을 만난다면 다리를 만들 수 없으며, 다른 섬을 만나..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 분리 집합, 그래프 이론, 그래프 탐색 설명 이미 갔던 도시를 또 다시 방문 및 경유하여 다른 도시로 가도 되므로, 가려고 하는 도시끼리 모두 이어져있는지 (같은 그룹에 있는지) 판단하면 될 것 같습니다. 이 문제에는 분리집합 알고리즘이 유용하게 쓰일 것 같네요. 분리집합 알고리즘을 모르신다면 아래 포스팅을 참고해주세요. https://uknowblog.t..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 꽤 유명한 물통 문제 입니다. 해당 문제에서는 모든 경우의 수를 탐색해야 하므로, DFS, BFS 중 어느것을 사용해도 무방하나 소스코드 import java.lang.StringBuilder import java.util.LinkedList import java.util.Queue..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 모든 정점에 대해 최단거리를 출력하는 문제입니다. BFS를 응용해 풀 수 있겠네요. BFS를 사용한 최단거리 문제는 아래 포스팅을 참고해주세요. https://uknowblog.tistory.com/24 [백준 2178번][Kotlin] 미로 탐색 https://www.acm..

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/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/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..