원하는 것은 뭐든지

문제풀이문제 해석1. 케빈 베이컨의 6단계 법칙은 "지구에 있는 모든 사람들은 6단계 이내에서 서로 아는 사람으로 연결될 수 있다."라는 법칙이다.2. 케빈 베이컨 게임은 임의의 두사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.3. 사람의 번호는 1부터 N까지이고, 승리자는 가장 작은 단계의 합을 가지고 있는 사람이다.4. 첫째 줄에 게임유저의 수 N, 관계의 수 M 이 주어진다.5. 둘째 줄 부터 관계 M개가 주어진다.6. 게임의 승리자를 찾아라, 같은 사람이 여려 명일 경우 숫자가 작은 사람이 이긴다. 문제 풀이1. 유저의 수가 100이하이고 모든 유저와의 관계를 나타내야 하므로 플로이드-워셜 알고리즘을 사용2. 플로이드-워셜의 알고리즘의 내부 조건으로는 x(출발),y(중간다리),z(..

문제풀이문제 해석1. 가중치가 없는 그래프가 주어진다.2. 행렬로 주어지는데 i, j좌표는 i가 j로 가는 간선이 있다는 뜻이다.3. i에서 출발해서 j까지 닿을 수 있다면 1로 아니면 0으로 표시한다풀이 방법1. 정점이 100개로 작다.2. 플로이드 - 워셜 알고리즘을 적용한다.코드package online.judge.baekjoon;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/** * 경로 찾기 * 실버 1 * 문제해석 * 0~n까지 값이 특정 인덱스에 닿을 수 있는지 알아보는 문제 * * 문제 풀이 * 플로이드-워셜을 사용해..

문제풀이문제 해석1. N개의 영단어가 주어질 때, 가장 비슷한 단어를 구해야 한다.2. 비슷한 정도는 접두사의 길이, 즉 앞단어가 얼마나 비슷한지가 쟁점이다.3. 접두사의 길이가 최대인 경우가 여러 개 일 경우에는 앞쪽에 있는 단어를 출력한다.문제 풀이1. 공통부분문자열(Longest Common Substring)이지만 접두사만 보고 있기 때문에 알고리즘을 사용할 필요 없다.2. 시간제한이 2초이고 n이 20,000개 이기 때문에 단순 비교로도 구현 가능하다.3. 최대겹치는 부분의 길이보다 작은 문자열이라면 비교조차 할 필요 없다.소스코드package online.judge.baekjoon;import java.io.BufferedReader;import java.io.IOException;import..

문제풀이문제해석1. 우주선 ana호가 모든 행성을 탐사하는 최소시간을 계산하려고 한다.2. ana호는 자기 자신을 제외한 모든 행성으로 떠날 수 있다. 이것이 2차원 행렬로 주어진다.3. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라문제 풀이1. 행성의 개수가 많지 않아서 플로이드-워셜 알고리즘을 사용해도 괜찮다.2. 2차원 행렬이 주어지고 이를 가지고 플로이드-워셜 알고리즘을 적용하면 각 행성으로 가는 최소 시간을 구할 수 있다.3. 그 후 dfs를 통해 완전탐색을 해서 최소시간을 구한다.소스코드package online.judge.baekjoon;import java.util.Scanner;/** * 우주 탐사선 * 골드 3 */public class No17182 { static boo..