dfs

[백준, Java] 19621번 : 회의실 배정 2

🔗 문제 링크 https://www.acmicpc.net/problem/19621 😮 문제 해결 방법 문제의 제한 조건에서 K 번째 회의는 K-1 , K+1번째 회의와 겹친다고 했기 때문에 K 기준으로 회의를 참석하는 경우 K-1, K+1회의는 참석할 수 없다. 반대로 회의에 참가하지 않는 경우 K-1, K+1 회의는 참가할 수 있다. 따라서, 첫 회의를 기준으로 참가하는 경우와 불참하는 경우로 DFS를 이용한 완전탐색으로 문제를 해결했다. 회의의 최대 개수가25개까지 주어지므로 DFS를 이용한 완전탐색이 가능하다. 첫 번째 회의 기준으로 참가와 불참 경우로 탐색을 진행한다. 첫 번째 회의에 참가하는 경우 2번째 회의는 참가하지 못하기 때문에 3번째 회의에 참가하도록 depth + 2를 해주고 현재 회의..

[백준, Java] 9934번 : 완전 이진 트리

🔗 문제 링크 https://www.acmicpc.net/problem/9934 😮 문제 해결 방법 상근이가 도시를 방문한 조건을 살펴보면 가장 왼쪽에 있는 도시까지 방문한 후 그 부모를 방문 한 뒤 다시 오른쪽을 탐색한다. 즉, inorder 중위 순회 방식과 동일하다. 상근이가 방문한 도시의 트리 모양을 표현해줘야 하는 것이 목적이므로, 노드 번호가 1, 2, 3 순차적으로 증가하는 완전 이진 트리를 새로 만들어줬다. 새로 만든 트리를 이용해 중위 순회를 한 후 방문한 도시들을 스택에 저장한다. 입력으로 받은 도시와 스택에 저장한 도시가 동일한 순서이기 때문에 입력으로 받은 도시와 스택에 저장한 도시를 하나의 클래스로 매핑해준 뒤 새로 만든 트리의 모양대로 만들어준다. 새로 만든 트리는 노드 번호가 ..

[백준, Java] 1967번 : 트리의 지름

🔗 문제 링크 https://www.acmicpc.net/problem/1967 😮 문제 해결 방법 Map을 이용해 트리를 만들어 준다. 문제에서 루트노드가 1이라고 주어졌기 때문에 루트 노드를 이용해 가장 멀리 있는 노드를 먼저 탐색한다. 가장 먼 노드를 찾았다면, 해당 노드로 다시 가장 먼 노드를 탐색하면 노드와 노드간 가장 먼 지름이 탐색된다. 루트 노드를 이용해 DFS 탐색 및 가장 먼 노드 찾기 탐색한 가장 먼 노드를 이용해 다시 한번 DFS 탐색 및 지름 갱신 🚩 Java 코드 package com.algorithm.Baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReade..

[백준, Java] 1068번 : 트리

🔗 문제 링크 https://www.acmicpc.net/problem/1068 😮 문제 해결 방법 Map을 이용해 구현에 필요한 트리를 만들어 준 후 DFS를 이용해 루트 노드부터 탐색한다. Map에서 현재 노드에 해당하는 리스트가 없는 경우는 단말 노드이기 때문에 단말 노드 카운트를 증가시킨다. 현재 노드가 삭제할 노드인 경우는 다음 노드들은 모두 삭제 되므로 그대로 return한다. 만약 현재 노드에서 연결된 자식 노드가 삭제되는 노드이면서 단말 노드인 경우는 삭제 후 현재 노드가 단말노드가 되기 때문에 단말 노드 카운트를 증가시킨다. 🚩 Java 코드 package com.algorithm.Baekjoon; import java.io.BufferedReader; import java.io.IOEx..

[백준, Java] 1707번 : 이분 그래프

🔗 문제 링크 https://www.acmicpc.net/problem/1707 🤔 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 😮 문제 해결 방법 이분 그래프는 문제에 나와 있는 것 처럼 정점끼리 이어진 그래프를 하나의 집합으로 보고 서로 연결된 정점끼리는 다른 두 그룹으로 속하게 하는 그래프를 말한다. 따라서, 이분 그래프를 판별하는 방법은 다음과 같다. 색칠되지 않은 모든 정점에 대해 BFS를 진행한다. BFS의 시작 정점을 임의의 색상으로 색칠한다. ..