문제 11725번
: 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램
[입력]
: 첫째 줄에 노드의 개수 N
: 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점
[출력]
: 2 부터 N 노드까지 부모 노드 순서대로 출력
DFS
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
Stack 혹은 재귀함수로 구현
- 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가
더 이상 갈 수 없게되면 다른 방향으로 다시 탐색 진행 - 모든 노드를 방문하는 경우에 사용
ArrayList
- 본 코드에 arr 가 아닌 arraylist를 사용한 이유는 메모리초과 때문이다
- 배열과 차이점 : 배열은 크기가 고정, ArrayList는 크기가 가변적
- ArrayList는 자바의 List 인터페이스를 상속받은 클래스
- 일반 배열과 동일하게 연속된 메모리 공간을 사용하며 인덱스는 0부터 시작
- 현재 가용량 이상을 저장하려고 할 때 더 큰 공간의 메모리를 새롭게 할당
ArrayList 생성
자바에서 ArrayList를 사용하려면 아래 구문 추가
import java.util.ArrayList;ArrayList<Integer> integers1 = new ArrayList<Integer>(); // 타입 지정
ArrayList<Integer> integers2 = new ArrayList<>(); // 타입 생략 가능
ArrayList<Integer> integers3 = new ArrayList<>(10); // 초기 용량(Capacity) 설정
ArrayList<Integer> integers4 = new ArrayList<>(integers1); // 다른 Collection값으로 초기화
ArrayList<Integer> integers5 = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5)); // Arrays.asList() 데이터 수정
값 추가하기 - add()
값 변경하기 - set()
값 삭제하기 - remove(), clear()
값 읽기 - get()
[문제 과정]
| 입력 (연결된 정점) | x | y |
| 1 - 6 | 1 | 6 |
| 6 - 3 | 6 | 3 |
| 3 - 5 | 3 | 5 |
| 4 - 1 | 4 | 1 |
| 2 - 4 | 2 | 4 |
| 4 - 7 | 4 | 7 |
출처 https://dhbang.tistory.com/24
| < arr > |
||||||
| arr.get(x).add(y) 일 때 / arr.get(y).add(x) 일 때 | ||||||
| get (1) | get (2) | get (3) | get (4) | get (5) | get (6) | get (7) |
| 6 4 | 4 | 5 6 | 1 7 2 | 3 | 3 1 | 4 |
| DFS | arr | parent | |
| 초기 값 1 시작 | DFS(1) | arr[1] = 6, 4 | - |
| 6, 4 중에 6부터 시작 | DFS(6) | arr[6] = 3, |
parent[6] = 1 |
| 3, 1 중에 1은 방문했고 3부터 시작 | DFS(3) | arr[3] = 5, |
parent[3] =6 |
| 5, 6 중에 6는 방문했고 6부터 시작 | DFS(5) | arr[5] = |
parent[5] =3 |
| 6, 4 중에 6은 방문했고 4부터 시작 | DFS(4) | arr[4] = |
parent[4] =1 |
| 1, 7, 2 중에 1 방문했고 7부터 시작 | DFS(7) | arr[7] = |
parent[7] = 4 |
| 1, 7, 2 중에 1, 7 방문했고 2부터 시작 | DFS(2) | arr[2] = |
parent[2] = 4 |
| 결과 : parent = { 4, 6, 1, 3, 1, 4 } | |||
※ 맨 위 뿌리부터 타고 내려온다면 별다른 조건 없이도 루트를 구할 수 있다
[DFS 코드]
import java.io.*;
import java.util.*;
public class Main{
static int x,y,N;
static boolean visit[];
static int parent[];
static ArrayList<ArrayList<Integer>> arr=new ArrayList<>();
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
visit = new boolean[N+1];
parent = new int[N+1];
for(int i=0; i<=N;i++){
arr.add(new ArrayList<>());
}
for(int i =0; i<N-1; i++){
st= new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
arr.get(x).add(y);
arr.get(y).add(x);
}
DFS(1);
for(int i = 2;i<parent.length; i++){
System.out.println(parent[i]);
}
}
public static void DFS(int a){
visit[a] = true;
for (int i : arr.get(a)) {
if (!visit[i]) {
DFS(i);
parent[i]=a;
}
}
}
}
[해설]
: static int x,y,N; 입력값
static boolean visit[]; 방문기록
static int parent[]; 부모노드
static ArrayList<ArrayList<Integer>> arr=new ArrayList<>(); ArrayList 생성
: N = Integer.parseInt(br.readLine()); 첫번째 줄 입력
: visit = new boolean[N+1]; 방문기록 배열 생성 (노드 개수+1)
parent = new int[N+1]; 부모노드 배열 생성 (노드 개수+1)
: for(int i=0; i<=N;i++){
arr.add(new ArrayList<>()); arr 배열에 추가하기
}
: for(int i =0; i<N-1; i++){
st= new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken()); 둘째줄부터 받는 입력1
y = Integer.parseInt(st.nextToken()); 둘째줄부터 받는 입력2
arr.get(x).add(y); x번지에 y 값 추가
arr.get(y).add(x); y번지에 x 값 추가
}
DFS(1); 초기값 1노드부터 시작
for(int i = 2;i<parent.length; i++){
System.out.println(parent[i]); DFS에서 얻은 부모 노드 출력
}
: public static void DFS(int a){ a 초기값 = 1
visit[a] = true; 방문기록처리
for (int i : arr.get(a)) { arr의 a 번지에 있는 데이터 i에 저장
if (!visit[i]) { a번지의 데이터 방문처리
DFS(i); 해당 데이터 넣어 DFS 돌리기
parent[i]=a; a번지값을 parrent에 저장
}
}
}
[BFS 코드]
import java.io.*;
import java.util.*;
public class Main{
static ArrayList<Integer> arr[];
static int N,a,b,parent[];
static boolean visit[];
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
visit = new boolean[N+1];
parent = new int[N+1];
arr =new ArrayList[N+1];
for(int i=1; i<=N; i++){
arr[i] = new ArrayList<>();
}
for(int i=1; i<N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
a=Integer.parseInt(st.nextToken());
b=Integer.parseInt(st.nextToken());
arr[a].add(b);
arr[b].add(a);
}
bfs(1);
for(int i=2; i<=N; i++){
System.out.println(parent[i]);
}
}
static void bfs(int start){
Queue<Integer> q = new LinkedList<>();
q.add(start);
visit[start]=true;
while(!q.isEmpty()){
int p = q.poll();
for(int next:arr[p]){
if(!visit[next]){
visit[next]=true;
q.add(next);
parent[next]=p;
}
}
}
}
}
[해설]
: static ArrayList<Integer> arr[]; ArrayList로 한 번 더 감싸면 배열크기 안써도 된다
static int N,a,b,parent[];
static boolean visit[];
: BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine()); 입력1
visit = new boolean[N+1]; 방문
parent = new int[N+1]; 부모 저장
arr =new ArrayList[N+1]; 배열 초기화
: for(int i=1; i<=N; i++){
arr[i] = new ArrayList<>(); 인덱스 생성
}
: for(int i=1; i<N; i++){ N-1개 만큼 반복해서 입력 추가
StringTokenizer st = new StringTokenizer(br.readLine());
a=Integer.parseInt(st.nextToken());
b=Integer.parseInt(st.nextToken());
arr[a].add(b);
arr[b].add(a);
}
: bfs(1); 출력은 2지만 뿌리부터 시작해야 차근차근 다 구할 수 있다
: for(int i=2; i<=N; i++){ 출력은 2부터
System.out.println(parent[i]);
}
: static void bfs(int start){
Queue<Integer> q = new LinkedList<>(); 큐선언
q.add(start); 큐추가
visit[start]=true; 방문체크
while(!q.isEmpty()){
int p = q.poll(); 큐에서 빼기
for(int next:arr[p]){ 배열 안에 원소 모두 꺼내서 보기
if(!visit[next]){ 방문하지 않았다면
visit[next]=true; 방문체크
q.add(next); 큐추가
parent[next]=p; 원소의 부모는 해당 인덱스
}
}
}
}
이제 풀어보러 갈께요 :)
11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
www.acmicpc.net
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *
'Baekjoon > [5] DFS & BFS' 카테고리의 다른 글
| [백준] 7576번 토마토 JAVA (자바) 풀이 (0) | 2023.09.21 |
|---|---|
| [백준] 7569번 토마토 JAVA (자바) 풀이 (1) | 2023.09.21 |
| [백준] 7562번 나이트의 이동 JAVA (자바) 풀이 (0) | 2023.09.17 |
| [백준] 11724번 연결 요소의 개 JAVA (자바) 풀이 (0) | 2023.09.16 |
| [백준] 4963번 섬의 개수 JAVA (자바) 풀이 (0) | 2023.09.15 |
