반응형
12-23 19:41
- Today
- Total
Link
개발하는 고라니
[백준] 4803번 : 트리 본문
반응형
[DFS]
다수의 테스트 케이스 중 DFS를 이용해 사이클이 존재하는 것을 찾아 제외하고, 트리의 개수를 찾는 문제이다. 트리의 특징은 문제에서 잘 나타내어주고 있으며, 정점이 하나만 있는 것 역시 트리라고 본다. 문제의 입력과 출력이 번거로워서 그렇지 문제 자체의 난이도는 크게 어렵지 않다고 생각된다.
사이클을 찾는 방법은 글로 푸는 것 보다 코드가 간단하므로 코드를 보는 것이 더 빠르게 이해가 될 것 같다.
static boolean DFS(int x, int before){
if(visit[x])
return false;
boolean result = true;
visit[x] = true;
for(int next:list[x])
if(next != before)
result &= DFS(next, x);
return result;
}
위 코드는 DFS 메서드인데, boolean 타입을 반환한다. 반환 값이 true이면 트리라는 뜻이고, false면 사이클이 존재하므로 그래프가 된다.
# Code </>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static List<Integer>[] list;
static boolean[] visit;
static boolean DFS(int x, int before){
if(visit[x])
return false;
boolean result = true;
visit[x] = true;
for(int next:list[x])
if(next != before)
result &= DFS(next, x);
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = 1;
while(true){
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
if(n == 0 && m == 0) break;
list = new ArrayList[n+1];
visit = new boolean[n+1];
for(int i=1; i<=n; i++){
list[i] = new ArrayList<>();
}
for(int i=0; i<m; i++){
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
list[v1].add(v2);
list[v2].add(v1);
}
int cnt = 0;
for(int i=1; i<=n; i++)
if(!visit[i] && DFS(i, 0))
cnt++;
sb.append(String.format("Case %d: ", t++));
if(cnt == 0) sb.append("No trees.");
else if(cnt == 1) sb.append("There is one tree.");
else sb.append(String.format("A forest of %d trees.", cnt));
sb.append('\n');
}
System.out.print(sb);
}
}
반응형
'Programming > 백준' 카테고리의 다른 글
[백준] 1181번 : 단어 정렬 (0) | 2022.02.01 |
---|---|
[백준] 12763번 : 지각하면 안 돼 (0) | 2021.05.30 |
[백준] 18405번 : 경쟁적 전염 (0) | 2021.05.26 |
[백준] 3709번 : 레이저빔은 어디로 (0) | 2021.05.13 |
[백준] 5430번 : AC (0) | 2021.05.12 |
Comments