-

케빈 베이컨의 6단계 법칙 1389https://www.acmicpc.net/problem/1389 [풀이 방법]이 문제 역시 dfs, bfs, 플로이드 와샬 알고리즘 등 다양한 방법으로 풀 수 있다.난 플로이드 와샬 알고리즘으로 풀어봐야지... 가장 간단한 방법인 것 같다. 1. 첫째 줄에 N과 K를 입력받는다. N은 정점, K는 간선의 수라고 생각했다. 2. relation이라는 N+1 X N+1 행렬을 생성 후 이후에 나오는 간선 정보들을 저장했다. 여기서, 1이 3을 알때 3도 1을 안다고 볼 수 있으므로 relation[1][3] = 1 relation[3][1] = 1 을 해준다. 3. 탐색을 시작한다.relation[r][k] != 0이고 relation[k][c] != 0 일때 -relat..

경로 찾기 11403https://www.acmicpc.net/problem/11403 [문제 풀이] 이 문제를 푸는 방법은 여러 가지가 있다. 나는 bfs, dfs, 플로이드 와샬 알고리즘 중 플로이드 와샬 알고리즘을 이용해 풀었다.플로이드와샬 알고리즘은 형태가 정해져있기 때문에 모든 경로를 탐색하는 문제에 적용하기 쉬운 것 같다. 1. 모든 입력은 0과 1로 이루어져있다. 나는 입력을 받은 후 int형으로 바꾸지 않고 String형 그대로 map에 저장했다. 2. 정점 r에서 k로 가는 경로가 존재하고, 정점 k에서 c로 가는 경로도 존재한다면 정점 r에서 c로 가는 경로 또한 존재한다고 볼 수 있기 때문에 map[r][c]를 1로 설정해 주면 된다. 3. 탐색을 모두 마치고 출력하면 끝. 12345..

K번째 수 11004https://www.acmicpc.net/problem/11004 [풀이]숫자의 최대 입력 개수가 꽤 크다.수 정렬하기 3번 문제가 생각나서 비슷하게 풀려고 했으나 입력받은 수의 범위가 -10^9 < A < 10^9여서 포기.정렬 하면 분명히 시간초과걸릴텐데.... 하며 고민하던 중퀵소트를 변형해서 풀어보기로 했다. 설명하기가 좀 애매한 관계로 소스코드를 참고해 보자 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.io.BufferedReader;import java.io.InputStreamReader;i..