공부공간

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 www.acmicpc.net 플로이드-워셜문제의 기본적인 형태이다. 그래프에서 전체의 최단경로를 구할때에 O(N^3)으로 구할수있다. For문을 돌면서 나와 인접..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 상당히 쫄았던 문제이다.. Union-Find 개념을 이용하여 접근하려니 접근방법이 잘 보이지 않았고, 워스트케이스에대해서 0.5초의 시간을 넘을 것같다는 생각이 들었다. 일단한번 서브셋을 구해서 나누어보자! 라는 생각으로 접근하였는데, 단순한 2번의 BFS로 해결되었다. 문제에 쫄면 안되겠다. import java.io.BufferedReader; import java.io.InputStreamReader; impo..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net 익은토마토가 주변에 안익은 토마토를 전파하면서 퍼지는 문제이다. 퍼질때에 값이 일정하게 ( 시간이 + 1 ) 씩 증가하므로 BFS로 퍼지는..