Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 스터디
- 리액트 네이티브 프로젝트 생성
- SQL
- 리액트 네이티브 시작하기
- 백준 4358번
- HTTP
- 깃 연동
- 리액트 네이티브
- 지네릭스
- React Native
- 깃허브 토큰 인증
- 백준
- 정리
- 데베
- 백준 4949번
- 모두의네트워크
- 백준 5525번
- 팀플회고
- 문자열
- 데이터베이스
- 모두의 네트워크
- 백준 4358 자바
- 모두를 위한 딥러닝
- 깃 터미널 연동
- 자바
- 깃허브 로그인
- 네트워크
- 딥러닝
- 머신러닝
- 모두를위한딥러닝
Archives
- Today
- Total
솜이의 데브로그
백준 1991번 ) 트리 순회 (java) 본문
https://www.acmicpc.net/problem/1991
문제
풀이
import java.io.*;
import java.util.*;
public class Main {
static class Node{
int left;
int right;
public Node(int left, int right){
this.left = left;
this.right = right;
}
}
static List<Node>[] list;
static int none = '.' - 'A';
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
list = new ArrayList[n+1];
for(int i=0; i<n; i++){
list[i] = new ArrayList<>();
}
for(int i=0; i<n; i++){
String line = br.readLine();
StringTokenizer st = new StringTokenizer(line," ");
int data = st.nextToken().charAt(0) - 'A';
int left = st.nextToken().charAt(0) - 'A';
int right = st.nextToken().charAt(0) - 'A';
list[data].add(new Node(left, right));
}
preorder(0);
System.out.println();
inorder(0);
System.out.println();
postorder(0);
}
static void preorder(int start){
for(Node node : list[start]) {
int l = node.left;
int r = node.right;
System.out.print((char)(start+'A'));
if( l != none) preorder(l);
if( r != none) preorder(r);
}
}
static void inorder(int start){
for(Node node : list[start]){
int l = node.left;
int r = node.right;
if(l!= none) inorder(l);
System.out.print((char)(start+'A'));
if(r!= none) inorder(r);
}
}
static void postorder(int start){
for(Node node : list[start]){
int l = node.left;
int r = node.right;
if(l!= none) postorder(l);
if(r!= none) postorder(r);
System.out.print((char)(start+'A'));
}
}
}
트리를 List<Node>[] list = new ArrayList[n]; 형식으로 구현하였다.
에지를 하나씩 따라가지 않고 연결리스트로 트리 구조 구현.
저장할때는 List[data] 로 찾을 수 있도록 정수형태로 변환해주었다. 따라서 캐릭터를 정수형으로 변환하였다.
순회 방법은 정석대로 풀이.
꼭 트리 형태 구현하는 것 기억해두기!!
'Algorithm > 백준' 카테고리의 다른 글
백준 2178번 ) 미로 탐색 (java) (0) | 2022.03.11 |
---|---|
백준 11659번 ) 구간 합 구하기4 (java) (0) | 2022.03.11 |
백준 1260번 ) DFS와 BFS (java) (0) | 2022.03.09 |
백준 2748번 ) 피보나치 수 2 (java) (0) | 2022.02.24 |
백준 2231번 ) 분해합 (java) (0) | 2022.02.24 |