문제 링크 : https://www.acmicpc.net/problem/11725 이 문제는 트리를 구현하는 기본적인 문제이다.루트노드가 1번으로 고정되어 있기 때문에 그저 양방향 인접 리스트로 그래프를 표현하고1번 노드부터 탐색하며 부모노드를 찾아주면 된다. 예제 입력 1번을 그래프로 표현하면 위와 같다.여기서 루트노드가 1번이기 때문에 루트노드부터 시작해서4번 노드의 부모는 1번, 6번 노드의 부모는 1번2번 노드의 부모는 4번, 7번 노드의 부모는 4번이런 식으로 순차적으로 부모를 찾아주면 된다.이 과정에서는 DFS나 BFS를 사용하면 된다. 그래프를 리스트로 표현할 때는 방향이 없는 간선이므로 이와 같이 인접리스트로 표현해주면 된다. package boj;import java.util.*;impo..

문제 링크 : https://www.acmicpc.net/problem/17472 문제 설명이 아주 자세하게 나와있다.일반적인 하나의 알고리즘을 이용하는 게 아닌 여러 알고리즘을 사용하여 해결할 수 있는 문제이다.우선 문제에서 구하고자 하는것을 보면 결국 모든 섬이 하나의 집합으로 만들어져야 하는데이때 최단거리를 구하는 문제이다. 얼핏 봤을 때 최소 신장 트리(MST) 알고리즘을 사용하면 될 것처럼 보인다.일반적인 MST알고리즘 문제는 간선과 정점을 직접 제공하는경우가 많다.하지만 이 문제에서는 아무것도 주어져있지 않다. 문제에서 주어진 그림을 자세히 보면 힌트를 주듯 각 섬을 하나의 번호로 묶은 것을 볼 수 있다.따라서 문제를 해결하는 과정은 아래와 같다.1. 섬을 정점이라고 생각하고 맞닿아 있는 점끼..

문제 링크 : https://www.acmicpc.net/problem/18352 위의 문제는 전형적인 그래프를 이용한 문제이다.정점과 정점 사이의 간선의 길이가 모두 1이기 때문에 가중치가 없는 그래프라고 생각하면 된다. ArrayList []로 그래프를 표현하고 시작 정점으로부터 BFS로 순회하며 시작 정점과 떨어진 거리가 K인 정점을 찾으면 된다.시간을 좀 더 줄이기 위해 break에 라벨을 달아 바로 while 문이 종료될 수 있도록 했다. (방문배열을 -1 로 초기화하여 방문여부를 판단해도 괜찮다.)package boj;import java.util.*;import java.io.*;public class BOJ18352 { static int K; static int N; st..

문제 링크 : https://www.acmicpc.net/problem/1167 트리는 순환하지 않는다는 특징을 가지고 있고그렇기에 위에 문제에서 하나의 정점에서 다른 하나의 정점까지의 거리는 하나가 나온다.트리의 임의의 정점을 2개 골랐을 때 그 정점사이의 거리가 가장 긴 경우를 지름이라고 한다. 단순히 생각해보면 모든 정점 간의 거리를 구하면 될 것 같지만 정점의 수가 100,000 이기 때문에 시간초과가 발생한다.따라서 탐색의 범위를 줄여야 한다. 해당 문제를 풀때 아이디어는 임의의 한 정점에서 시작해서 다른 정점까지의 거리를 모두 구한 뒤 그중가장 멀리있는 정점이 해당 트리의 지름의 한 끝점이라는 것이다. 트리의 지름의 한 끝점을 구할 때 BFS를 한번 쓰고, 해당 끝점에서 BFS를 사용하여 각 ..