Java/Algorithms

문제 접근 방식 그래프가 주어졌을 때 해당 그래프에 트리가 몇 개 존재하는지를 구하는 문제다. 즉, 하나의 정점에서 출발하여 갈 수 있는 모든 정점까지 갔을 때 사이클이 존재하지 않으면 하나의 트리라고 볼 수 있고 이렇게 탐색을 했을 때 방문한 정점이 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..

문제 접근 방식 DFS와 BFS 방식으로 탐색하는 순서를 순서대로 출력하면 된다. 문제를 대충 보고 인접 리스트로 풀었더니 예제가 틀리길래 다시보니 작은 번호의 정점부터 방문하는 조건이 있어서 인접 행렬로 바꿔 풀었다. 양방향 그래프이기 때문에 양쪽 간선에 모두 이동할 수 있게 인접 행렬에 표시해주고 DFS와 BFS 순서대로 탐색을 진행해주면서 정점에 방문할 때마다 출력해주면 된다. 풀이 public class Main { private static int n; private static int[][] nearArr; private static boolean[] isVisited; private static StringBuilder sb = new StringBuilder(); public static ..

문제 접근 방식 끊기지 않고 연결된 묶음이 몇 개인지 찾는 문제로 BFS와 DFS 둘 중 아무거나 사용해서 풀 수도 있고, 인접 행렬이나 인접 리스트 중 아무거나 사용해도 상관없기에 BFS를 사용해서 인접 행렬과 인접 리스트 둘 다 사용해 풀어봤다. 문제에서 주어진 그래프는 무방향 그래프이기 때문에 인접 행렬이나 리스트를 만들 때 (x, y)와 (y, x) 모두 추가해줘야 한다. 인접 행렬의 경우에는 0과 1로 구분해서 간선이 존재하는 경우를 1로 표현해주면 되고 인접 리스트의 경우에는 해당 정점에서 이동할 수 있는 정점을 추가해주면 된다. 풀이 인접 행렬을 사용한 풀이 public class Main { public static void main(String[] args) throws IOExcepti..