30번(13116)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
/*
* 1. 트리에서 자식노드 값을 2로 나누면 부모노드의 값을 구할 수 있다
* 2. a와 b를 2로 나누면서 쭉 부모노드로 올라감
* 3. 서로 공통되는 부모노드중 최댓값을 찾아야 하기때문에 a와 b중 큰값을 먼저 나눔. 값이 같아지면 반복 멈춤*/
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int a, b;
StringTokenizer st;
StringBuilder sb = new StringBuilder();
while (t-- > 0) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
while (a != b) {
if (a > b) {
a /= 2;
} else if (b > a) {
b /= 2;
}
}
sb.append(b * 10).append("\n");
}
System.out.println(sb);
}
}
완전 이진 트리(9934)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static List<Integer>[] levels;
static int[] numbers;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int k = Integer.parseInt(br.readLine());
int size = (int) (Math.pow(2, k) - 1); // 트리의 노드 개수 저장
// 입력으로 주어진 트리의 중위순회 결과를 배열에 저장
numbers = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
//트리의 레벨별 노드값들을 리스트에 저장
levels = new ArrayList[k];
for (int i = 0; i < k; i++) { // 트리의 레벨만큼 리스트배열 초기화
levels[i] = new ArrayList<>();
}
// 중위순회 결과로 트리 구성
makeTree(0, size - 1, 0); // start, end, depth
StringBuilder sb = new StringBuilder();
for (int i = 0; i < levels.length; i++) {
// 트리의 레벨별로 노드 값들을 한줄씩 출력
for (int node : levels[i]) {
sb.append(node).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
static void makeTree(int start, int end, int depth) {
if (start > end) return;
int mid = (start + end) / 2;
levels[depth].add(numbers[mid]);
// 왼쪽 하위 트리 구성
makeTree(start, mid - 1, depth + 1);
// 오른쪽 하위 트리 구성
makeTree(mid + 1, end, depth + 1);
}
}
숫자판 점프(2210)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
static int[] dx = {-1, 1, 0, 0}; // 상하
static int[] dy = {0, 0, -1, 1}; // 좌우
static int[][] graph = new int[5][5];
static Set<String> resultSet = new HashSet<>(); // 그래프의 첫요소부터 마지막요소까지 모두 탐색하여 set에 저장하기 위함
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// 입력받은 숫자판대로 2차원배열에 저장
for (int i = 0; i < 5; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 5; j++) {
graph[i][j] = Integer.parseInt(st.nextToken());
}
}
// 첫 요소부터 탐색 시작
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
dfs(i, j, 0, ""); // 좌표x, 좌표y, 6자리의 수를 만들기위한 depth, 빈 문자열로 시작
}
}
System.out.println(resultSet.size());
}
static void dfs(int x, int y, int depth, String str) {
if (depth == 6) { //depth 가 6이면 문자열의 길이가 6이므로 해당 문자열 Set에 추가하고 재귀종료
resultSet.add(str);
return;
}
str += graph[x][y]; // 현재 좌표의 문자열을 추가
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i]; // 다음 좌표로 이동
// 이동된 좌표가 배열의 인덱스 범위 밖이라면 다음 순회로 넘어감
if (nx < 0 || nx > 4 || ny < 0 || ny > 4) continue;
// 유효한 좌표라면 해당 좌표 탐색
dfs(nx, ny, depth + 1, str);
}
}
}
양치기 꿈(3187)
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 Main {
static int[] dx = {-1, 1, 0, 0}; // 상하
static int[] dy = {0, 0, -1, 1}; // 좌우
static char[][] farm;
static int r, c, sumSheep, sumWolf; // 행, 열, 양 총합, 늑대 총합
static boolean[][] visited; // 이미 탐색한 좌표인지 기록하기 위함
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
farm = new char[r][c];
visited = new boolean[r][c];
// 입력받고 배열에 저장
for (int i = 0; i < r; i++) {
farm[i] = br.readLine().toCharArray();
}
// 농장의 모든 좌표 탐색 시작
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
// 방문하지 않았으며 해당 좌표가 양이나 늑대인 경우 bfs탐색 시작
if ((farm[i][j] == 'k' || farm[i][j] == 'v') && !visited[i][j]) {
bfs(i, j);
}
}
}
System.out.println(sumSheep + " " + sumWolf);
}
static void bfs(int i, int j) {
// 좌표를 배열에 저장하고 큐에 저장
Queue<int[]> q = new LinkedList<>();
visited[i][j] = true; // 해당 좌표를 방문한 것으로 표시
q.add(new int[]{i, j}); // 너비우선탐색을 위해 좌표정보 큐에 추가
int sheep = 0, wolf = 0; // 해당 탐색에서 양과 늑대가 몇마리인지 저장하기 위한 변수
// 현재좌표의 동물 카운트
if (farm[i][j] == 'v') wolf++;
else if (farm[i][j] == 'k') sheep++;
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int k = 0; k < 4; k++) {
int nx = cur[0] + dx[k]; // 이동 좌표
int ny = cur[1] + dy[k];
// 농장 밖으로 벗어나거나 방문했던 좌표이거나 울타리가 있다면 다음순회로 넝머감
if (nx < 0 || nx >= r || ny < 0 || ny >= c || visited[nx][ny] || farm[nx][ny] == '#') continue;
// 이동한 좌표의 동물을 구별하고 해당 동물 카운트
if (farm[nx][ny] == 'v') wolf++;
else if (farm[nx][ny] == 'k') sheep++;
visited[nx][ny] = true;
q.add(new int[]{nx, ny}); // 다음 탐색을 위해 큐에 추가
}
}
// 탐색한 공간에서 많은쪽의 동물들만 살아남으므로 해당되는 동물을 합계에 추가
if (sheep > wolf) {
sumSheep += sheep;
} else {
sumWolf += wolf;
}
}
}