분류 전체보기

문제 접근 방식 이전까지의 트리 문제에서는 각 노드 간의 거리가 1이였다면 이번 문제에서는 노드 간 거리가 서로 다르게 주어진다. 그래서 인접 리스트를 만들 때 기존에는 각 각선의 양끝 정점에 대해서만 넣어줬다면 이번에는 정점 간의 거리도 넣어준 후에 탐색만 해주면 된다. 풀이 public class Main { private static int start, end, result; private static boolean[] isVisited; private static final ArrayList near = new ArrayList(); public static void main(String[] args) throws IOException { BufferedReader br = new Buffered..

문제 접근 방식 정점이 N개이고 루트가 R인 올바른 트리에 대한 간선이 주어졌을 때 정점이 U인 경우에는 몇 개의 정점을 방문할 수 있는지를 알아내면 된다. 예를 들어 위와 같은 트리가 있을 때를 생각해보면 루트인 5번 정점부터 방문하면 당연히 모든 정점인 9개의 정점을 다 방문할 수 있다. 하지만 4번 정점부터 방문한다면 위와 같이 4개의 정점만 방문할 것이고 8번 정점부터 방문한다면 8번 하나만 방문할 수 있다. 이제 특정 정점에 포함된 정점의 개수가 몇 개인지를 알아내면 되는데 이는 트리의 성질을 이용하면 쉽게 계산할 수 있다. 위의 트리를 다시 살펴보면 정점 3의 경우는 자기 자신을 포함한 자식 노드의 정점 수의 합인 3이고 정점 4의 경우도 마찬가지로 자기 자신을 포함한 자식 노드인 3번 노드의..

문제 접근 방식 그래프가 주어졌을 때 해당 그래프에 트리가 몇 개 존재하는지를 구하는 문제다. 즉, 하나의 정점에서 출발하여 갈 수 있는 모든 정점까지 갔을 때 사이클이 존재하지 않으면 하나의 트리라고 볼 수 있고 이렇게 탐색을 했을 때 방문한 정점이 n개, 간선이 n-1개라면 트리라는 것을 알 수 있다. 무방향 그래프에서 트리를 찾는 것이기 때문에 (n - 1) * 2개의 간선이 있는지 확인하여 맞다면 트리의 개수를 1씩 증가시켜주면 된다. 정점을 처음 방문할 때마다 정점의 개수를 카운팅 해주고 해당 정점에 있는 모든 간선을 확인할 때마다 간선의 개수를 카운팅 하고 아직 방문하지 않은 정점인 경우에만 방문해준다. 한 정점에서의 탐색이 모두 끝났다면 현재까지 기록된 정점과 간선의 개수가 트리의 기준에 만..

문제 접근 방식 그래프에서의 BFS/DFS와 조금만 다르게 코드를 짜면 트리를 순회할 수 있는 BFS/DFS 코드를 만들 수 있다. 기존에 그래프에서는 이전에 방문한 정점인지 확인하기 위해 불리언이나 정수형 배열을 통해 방문 여부를 기록해두었다면 트리는 방문 여부를 확인하는 것이 아니라 부모가 기록 되었는지로 방문 여부를 확인할 수 있다. 기존 BFS/DFS 코드와 마찬가지로 구성은 같지만 다음에 방문할 자식 노드에 부모가 누구인지만 기록해주면 된다. BFS와 DFS 방식 모두 구현해보았는데 그래프 때도 느꼈지만 재귀 방식인 DFS가 코드가 뭔가 깔끔해서 보기가 좋다. 풀이 public class Main { private static int n; private static int[] p; private..

문제 접근 방식 입력이 복잡하게 주어져서 이걸 어떻게 간선으로 표현할지 난감했는데 결국 진실을 아는 사람들과 연결된지만 확인하여 진실을 아는 사람, 그 사람들과 만난 적 있는 사람들이 참여한 파티라면 전체 파티 수에서 1씩 빼주면 된다. 우선 입력을 받을 때, 같은 파티에 참여한 사람들끼리 서로 인접 그래프에 동일하게 추가해준 후에, 진실을 아는 사람들만 시작 정점으로 하여 DFS로 탐색을 해주면서 방문한 모든 정점들을 참으로 바꿔주면 진실을 아는 사람과 만난 사람들이 누군지까지 알 수 있다. 그 후에 파티 참가자들을 확인하면서 진실을 아는지 확인해주면 된다. 풀이 public class Main { private static ArrayList near = new ArrayList(); private s..

문제 접근 방식 각각의 구슬을 정점, 두 구슬의 대소 관계를 간선이라고 했을 때 정점 X에서 Y로 갈 수 있다면 구슬 X가 구슬 Y보다 무겁다는 것을 알 수 있다. 하지만 단방향 그래프로 인접 행렬을 표현하니 대소 관계가 제대로 처리가 되지 않고 일반적인 양방향으로 표현하자니 어느 구슬이 무거운지를 알 수가 없는 문제가 있었다. 그래서 인접 행렬을 만들 때 구슬 X가 Y보다 무겁다면 정점 X에서 Y로 갈 수 있는 것을 표시할 때 1로 표시를 해주고 구슬 X가 Y보다 가볍다면 -1로 표시를 해주었다. 그 후 각 구슬마다 DFS로 탐색을 해주면서 다음 방문할 정점이 1인지 -1인지에 따라 각 수마다 더 큰 수와 작은 수의 개수를 카운트 해주고 모든 정점에 대한 탐색이 끝나면 카운트를 저장해둔 배열을 순회하며..

문제 접근 방식 이분 그래프의 개념만 알면 BFS나 DFS로 쉽게 풀 수 있는 문제다. 위와 같은 그래프가 주어졌을 때 DFS 탐색 순서는 아래와 같다. 1 > 2 > 3 > 4 > 2 > 4 이분 그래프는 모든 정점을 두 가지 색으로만 칠할 수 있다고 생각하면 되는데 인접한 정점을 방문할 때마다 현재 정점과 반대되는 색깔로 칠하다 만약 다음에 방문할 정점이 이미 색이 칠해져있고 현재 정점과 색깔이 같다면 이분 그래프가 아니라는 것을 알 수 있다. 1번 정점 방문 => 1번 정점 빨간색으로 색칠 2번 정점 방문 => 2번 정점 파란색으로 색칠 3번 정점 방문 => 3번 정점 빨간색으로 색칠 4번 정점 방문 => 4번 정점 파란색으로 색칠 2번 정점 방문 => 2번 정점 빨간색으로 색칠 (이미 파란색인데 ..

문제 접근 방식 한 사람이 모든 사람을 친구의 친구의 친구...의 친구 까지 걸치고 걸쳐 모두 알 수 있다고 가정 했을 때 모든 사람을 알기 위해 필요한 단계가 가장 짧은 사람을 구해야 한다. 1 2 2 3 3 4 4 5 2 4 5 3 위와 같은 관계가 주어졌을 때 2번 사람의 경우를 살펴보면 아래와 같다. 본인 2 친구 1 3 4 친구의 친구 5 2번 자기 자신과 직접적으로 친구 관계인 1, 3, 4번이 있고 5번은 3번의 친구니 친구의 친구 관계이고 2번이 모든 사람을 알기 위해 필요한 단계는 친구의 친구까지다. 즉, 본인 0단계, 친구 1단계, 친구의 친구 2단계로 2단계만 거치면 모든 사람을 알 수 있다. 이때 조심해야 할 점은 2번이 5번을 알 수 있는 방법이 두 가지인데 첫 번째는 2 >> 3..