구르는 돌에는 이끼가 끼지 않는다

https://www.acmicpc.net/problem/11725

package com.ji.beakjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class SearchParentsTree {

	static int nodeNum, edgeNum;
//	static int[][] graph;
	static ArrayList<Integer> ad[];
	static boolean[] DFSisVisited;
	static int result[];

	public static void main(String[] args) throws IOException {

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		nodeNum = Integer.valueOf(br.readLine());
		DFSisVisited = new boolean[nodeNum + 1];
//		graph = new int[nodeNum + 1][nodeNum + 1];
		result = new int[nodeNum + 1];
		ad = new ArrayList[nodeNum +1];
		
		for(int i=1; i<=nodeNum; i++)
			ad[i] = new ArrayList<>();
		
		for (int i = 0; i < nodeNum - 1; i++) {
			String[] edgeNumbers = br.readLine().split(" ");
			int a = Integer.valueOf(edgeNumbers[0]);
			int b = Integer.valueOf(edgeNumbers[1]);
			ad[a].add(b);
			ad[b].add(a);
			
		}

		//메모리 초과!!!
//		for (int i = 0; i < nodeNum - 1; i++) {
//			String[] edgeNumbers = br.readLine().split(" ");
//			int a = Integer.valueOf(edgeNumbers[0]);
//			int b = Integer.valueOf(edgeNumbers[1]);
//			graph[a][b] = b;
//			graph[b][a] = a;
//		}

		dfs(1);
		for (int i = 2; i <= nodeNum; i++)
			bw.write(result[i] + "\n");

		bw.flush();
		bw.close();
	}
	
	static void dfs(int node) {
		// 방문한 노드 번호에 대한 boolean 처리
		DFSisVisited[node] = true;
		for(int index : ad[node]) {
			if(!DFSisVisited[index]) {
				result[index] = node;
				dfs(index);
			}
		}
	}

}

https://www.acmicpc.net/problem/1991

package com.ji.beakjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class TreeTraversal {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		Tree tree = new Tree();

		for(int i = 0; i < N; i++) {
			char[] data;
			data = br.readLine().replaceAll(" ", "").toCharArray();
			tree.createNode(data[0], data[1], data[2]);
		}
		
		//전위 순회 
		tree.preorder(tree.root);
		System.out.println();
	
		//중위 순회 
		tree.inorder(tree.root);
		System.out.println();
		
		//후위 순회 
		tree.postorder(tree.root);
		
		br.close();
	}
	
}

class Node {
	char data;
	Node left;
	Node right;
	
	Node(char data) {
		this.data = data;
	}
}

class Tree {
	
	Node root; //루트 노드 처음엔 null 상태 
	public void createNode(char data, char leftData, char rightData) {
		if(root == null) { //아무것도 없는 초기 상태 - A 루트 노드 생성 
			root = new Node(data);
			
			//좌우 값이 있는 경우에만 노드 생성 
			if(leftData != '.') { 
				root.left = new Node(leftData);
			}
			if(rightData != '.') {
				root.right = new Node(rightData);
			}
		} else { //초기상태가 아니면 어디에 들어가야할지 찾아야함 - A 루트 노드 이후 
			searchNode(root, data, leftData, rightData);
		}
	}
	
    //여기에서 root는 매개 변수로 들어온 로컬변수 root임을 주의 
	public void searchNode(Node root, char data, char leftData, char rightData) { 
		if(root == null) { //도착한 노드가 null이면 재귀 종료 - 찾을(삽입할) 노드 X
			return;
		} else if(root.data == data) { //들어갈 위치를 찾았다면 
			if(leftData != '.') { //.이 아니라 값이 있는 경우에만 좌우 노드 생성 
				root.left = new Node(leftData);
			}
			if(rightData != '.') {
				root.right = new Node(rightData);
			}
		} else { //아직 찾지못했고 탐색할 노드가 남아 있다면 
			searchNode(root.left, data, leftData, rightData); //왼쪽 재귀 탐색 
			searchNode(root.right, data, leftData, rightData); //오른쪽 재귀 탐색 
		}
	}
	
	// 전위순회 : 루트 -> 좌 -> 우 
	public void preorder(Node root){
		System.out.print(root.data); //먼저 가운데 출력
		if(root.left!=null) preorder(root.left); //그 다음 왼쪽
		if(root.right!=null) preorder(root.right); //마지막 오른쪽
	}
	
	// 중위순회 : 좌 -> 루트 -> 우
	public void inorder(Node root){
		if(root.left!=null) inorder(root.left); //왼쪽 먼저
		System.out.print(root.data); //그 다음 중앙 출력
		if(root.right!=null) inorder(root.right); //마지막으로 오른쪽
	}
	
	// 후위순회 : 좌 -> 우 -> 루트 
	public void postorder(Node root){
		if(root.left!=null) postorder(root.left); //왼쪽 먼저
		if(root.right!=null) postorder(root.right); //그 다음 오른쪽
		System.out.print(root.data);
	}
	
}

https://www.acmicpc.net/problem/15653

package com.ji.beakjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class MarbleEscape4_Study {
	
	static class Node{
		int r, c, time; 
		char type; 
		
		Node(int r, int c, char type, int time){
			this.r = r; 
			this.c = c;
			this.type =type; 
			this.time = time;
		}
	}
	
	static Queue<Node> q;
	static boolean[][][][] visited;
	static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static char[][] map;
	static int blueR, blueC, redR, redC;
	static int N, M; 
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		q = new LinkedList<>();
		visited = new boolean[N][M][N][M];
		map = new char[N][M];

		for (int r = 0; r < N; ++r) {
			char[] line = br.readLine().toCharArray();
			for (int c = 0; c < M; ++c) {
				if (line[c] == 'R') {
					map[r][c] = '.';
					redR = r;
					redC = c;
					q.offer(new Node(r, c, line[c], 0));
				} else if (line[c] == 'B') {
					map[r][c] = '.';
					blueR = r;
					blueC = c;
					q.offer(new Node(r, c, line[c], 0));
				} else {
					map[r][c] = line[c];
				}
			}
		}

		visited[redR][redC][blueR][blueC] = true;

		System.out.println(bfs());
			
	}

	private static int bfs() {
		while (!q.isEmpty()) {
			Node blue, red;
			if (q.peek().type == 'B') {
				blue = q.poll();
				red = q.poll();
			} else {
				red = q.poll();
				blue = q.poll();
			}

			boolean blueInHole, redInHole, afterRed;
			int bcr, bcc, rcr, rcc;
			int bnr, bnc, rnr, rnc;
			for (int d = 0; d < 4; ++d) {
				blueInHole = redInHole = afterRed = false;
				bcr = blue.r;
				bcc = blue.c;
				rcr = red.r;
				rcc = red.c;

				// 파랑 구슬 이동
				while (true) {
					bnr = bcr + dir[d][0];
					bnc = bcc + dir[d][1];
					if (bnr == rcr && bnc == rcc)
						afterRed = true;
					if (map[bnr][bnc] == '#')
						break;
					if (map[bnr][bnc] == 'O') {
						blueInHole = true;
						break;
					}
					bcr = bnr;
					bcc = bnc;
				}

				// 빨강 구슬 이동
				while (true) {
					rnr = rcr + dir[d][0];
					rnc = rcc + dir[d][1];
					if (map[rnr][rnc] == '#')
						break;
					if (map[rnr][rnc] == 'O') {
						redInHole = true;
						break;
					}
					rcr = rnr;
					rcc = rnc;
				}

				// 파란구슬이 들어갔을 때
				if (blueInHole)
					continue;
				// 빨간구슬이 들어갔을 때
				if (redInHole)
					return red.time + 1;

				// 구슬이 겹쳤을 때
				if (bcr == rcr && bcc == rcc) {
					// 빨간구슬 다음에 파란구슬이 올 때
					if (afterRed) {
						bcr -= dir[d][0];
						bcc -= dir[d][1];
						// 파란구슬 다음에 빨간구슬이 올 때
					} else {
						rcr -= dir[d][0];
						rcc -= dir[d][1];
					}
				}
				// 방문체크
				if (visited[rcr][rcc][bcr][bcc])
					continue;
				visited[rcr][rcc][bcr][bcc] = true;

				q.offer(new Node(bcr, bcc, 'B', blue.time + 1));
				q.offer(new Node(rcr, rcc, 'R', red.time + 1));
			}
		}

		return -1;
	}

}