문제 링크 : https://www.acmicpc.net/problem/1068 문제 자체는 리프노드의 개수를 세는 문제로 단순하다.하지만 단순 리프노드를 세는 게 아닌 중간에 노드를 삭제했을 때 리프노드의 개수를 구해야 한다. 문제를 2가지 방법을 해결해봤다.첫 번째 방법첫 번째는 자식노드의 개수를 직접 카운팅 하여 자식노드가 없는 노드의 개수를 세는 방식이다.먼저 노드를 삭제하기 이전의 자식노드 개수로 counts배열을 초기화한다.이후 만약 2번 노드를 삭제한다면 2번 노드의 부모노드인 0번 노드의 자식개수를 1개 빼준다.그다음 2번 노드와 2번 노드의 자식들은 자식노드의 개수를 -1로 바꿔준다. package boj;import java.util.*;import java.io.*;public cla..

문제 링크 : https://www.acmicpc.net/problem/1707 위의 문제는 그래프를 2개의 집합으로 나누었을 때 각각의 집합에 인접한 정점이 없는지를 확인하는 문제이다.단순히 생각해 보면 한 정점의 바로 옆에 있는 정점을 다른 집합으로 정했을 때 문제가 없을지 확인하면 된다.경우의 수를 생각해 보면 아래와 같은 경우가 있다. 첫 번째로 만약 일직선의 경우 1번 노드를 0 집합에 넣고2번 노드를 1 집합 3번 노드를 0 집합에 넣는다면 해당 그래프는 이분 그래프라고 할 수 있다. 따라서 일직선의 경우에는 이분 그래프의 조건을 만족한다. 두 번째로 순환그래프 중 문제가 발생하는 경우이다.홀수개로 이루어진 정점이 순환되는 위와 같은 형태의 그래프에서는1번과 3번 노드가 둘 다 0 집합에 들어..

문제 링크 : https://www.acmicpc.net/problem/13023 이 문제는 5개 이상의 정점이 이어져있는지를 묻는 문제이다.모든 경우의 수를 다 봐야 하며 정점(사람의 수) = 최대 2000간선(친구관계의 수) = 최대 2000 이기 때문에 만약 모든 정점을 기준으로 DFS 탐색을 실시한다고 하면 O((2000 + 2000) * 2000)으로 시간복잡도상 충분히 시간 내에 풀 수 있다. 추가로 가지치기를 통해서 연산량을 줄이고단순 DFS를 이용하면 풀 수 있다. package boj;import java.util.*;import java.io.*;public class BOJ13023 { static List> graph = new ArrayList(); static bool..