Coding Test/BOJ

[BOJ/JAAVA] 1967번: 트리의 지름

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 키워드 트리의 지름 : 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. 구현 주어진 정보를 이용하여 트리를 구현한다. 모든 노드를 돌면서 현재 노드 위치를 루트로 하는 서브트리에서 루트를 무조건 거치는 최대 길이를 구한다. 코드 import java.io.BufferedReader; import java.io.IOException; impor..

[BOJ/JAVA] 15681번: 트리와 쿼리

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 키워드 • 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다. 구현 어떤 것이 부모노드이고 어떤 것이 자식 노드인지 알 필요가 있다. 루트번호 R을 이용하여 DFS를 사용하고, 해당 노드의 부모노드를 알아낸다. 이후 DP를 사용하여 해당 노드 번호의 서브트리에 속한 정점의 수를 저장한다. 코드 import java.io.Bu..

[BOJ/JAVA] 9934번: 완전 이진 트리

https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 키워드 가장 처음에 상근이는 트리의 루트에 있는 빌딩 앞에 서있다. 현재 빌딩의 왼쪽 자식에 있는 빌딩에 아직 들어가지 않았다면, 왼쪽 자식으로 이동한다. 현재 있는 노드가 왼쪽 자식을 가지고 있지 않거나 왼쪽 자식에 있는 빌딩을 이미 들어갔다면, 현재 노드에 있는 빌딩을 들어가고 종이에 번호를 적는다. 현재 빌딩을 이미 들어갔다 온 상태이고, 오른쪽 자식을 가지고 있는 ..

[BOJ/JAVA] 11725번: 트리의 부모 찾기

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 키워드 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 구현 중요한 점은 이진트리가 아니라는 점이다. 1번 노드부터 DFS를 하면서 부모의 정보를 넘겨주면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; impo..

[BOJ/JAVA] 11559번: Puyo Puyo

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 키워드 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다. 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다. 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다. 구현 정리하면 연쇄는 **중..

[BOJ/JAVA] 20055 컨베이어 벨트 위의 로봇

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 키워드 로봇은 올리는 위치에만 올릴 수 있다. 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다. 로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다. 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 ..

[BOJ/JAVA] 14653번: 너의 이름은

https://www.acmicpc.net/problem/14653 14653번: 너의 이름은 첫째 줄에 OAKAK TALK방에 있는 사람 수 N과 총 메시지의 개수 K, 정보를 알고 싶은 메시지의 번호 Q가 주어진다. (1 ≤ N ≤ 26, 1 ≤ K ≤ 10,000, 1 ≤ Q ≤ K) 둘째 줄부터 K개의 줄에 걸쳐 메시지를 읽지 www.acmicpc.net 키워드 N명이 있는 OAKAK TALK방이 있다. 그리고 그 방에는 K개의 메시지가 있다. 만약 어떤 시점에 메시지를 읽거나 보냈다면, 그 시점 이전에 수신된 메시지는 모두 읽은 것으로 처리된다. N명의 이름은 A부터 사전 순서대로 N개의 알파벳이 부여된다. “나”의 이름은 A이고 “나”는 항상 모든 메시지를 읽는다. Q번째 메시지를 읽지 않은 ..

[BOJ/JAVA] 1063번: 킹

https://www.acmicpc.net/problem/1063 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 키워드 킹은 8방향으로 이동한다. 체스판에는 돌이 하나 있는데, 돌과 같은 곳으로 이동할 때는, 돌을 킹이 움직인 방향과 같은 방향으로 한 칸 이동시킨다. 킹이나 돌이 체스판 밖으로 나갈 경우에는 그 이동은 건너 뛰고 다음 이동을 한다. 구현 8방향 이동 Map을 구현한다. 체스판 좌표를 배열 좌표에 매핑시킨다. 배열의 범위를 벗어나는지 확인하는 메소드를 구현한다. 현재 이동하려는 위치에 돌이 있는지 확인한..

[BOJ/JAVA] 20058번: 마법사 상어와 파이어스톰

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 키워드 크기가 2^N × 2^N인 격자로 나누어진 얼음판 위치 (r, c)는 격자의 r행 c열을 의미 A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다. 파이어스톰 먼저 격자를 2^L × 2^L 크기의 부분 격자로 나눈다. 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 ..

[BOJ/JAVA] 1303번: 전쟁 - 전투

키워드 당신의 병사들은 **흰색 옷**을 입고, 적국의 병사들은 **파란색 옷**을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. N명이 뭉쳐있을 때는 **N^2의 위력**을 낼 수 있다. 구현 [0][0] 부터 깊이 우선 탐색을 하면서 각 탐색 마다 방문 횟수를 저장하고, 방문 횟수의 제곱을 결과 score에 누적합을 한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class java_1303 { final static int dydx[][] = { { -1, 0 }, { 1, 0 }, { ..