본문 바로가기

Java128

[백준] 1967번 트리의 지름 JAVA (자바) 풀이 문제 1967번 (dfs)  :  트리(tree)는 사이클이 없는 무방향 그래프    트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재    어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것 :  이런 두 노드 사이의 경로의 길이를 트리의 지름    입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해라  :  아래와 같은 트리가 주어진다면 트리의 지름은 45    [입력] :  파일의 첫 번째 줄은 노드의 개수 n (1 ≤ n ≤ 10,000) :  둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보 (세 개의 정수)    (연결하는 두 노드 중 부모 노드의 번호, 자식 노드, 간선의 가중치)     간선에 대한 정보는 부.. 2024. 8. 6.
[백준] 2573번 빙산 JAVA (자바) 풀이 문제 2573번 (BFS)  : 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장   바다 = 0        2453   3 252  7624           :  빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 준다    동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다 (0보다 더 줄어들지 않는다)             241   1 15   5412                                             1년 후 빙산  :  빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오    전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력   [입력] :  첫 줄에는 행의 개수와 열의.. 2024. 8. 6.
[백준] 15686번 치킨 배달 JAVA (자바) 풀이 문제 15686번 (백트래킹, 브루트포스)  :  크기가 N×N인 도시    도시의 각 칸은 빈 칸, 치킨집, 집 중 하나  :  사람들은 "치킨 거리"라는 말을 주로 사용    치킨 거리는 집과 가장 가까운 치킨집 사이의 거리    각각의 집은 치킨 거리를 가지고 있고 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.    거리는 |r1-r2| + |c1-c2|로 구한다  :  0은 빈 칸, 1은 집, 2는 치킨집    이 도시에 있는 치킨집은 모두 같은 프랜차이즈이며 일부 치킨집을 폐업시키려고 한다    이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개    나머지 치킨집은 모두 폐업시켜야 한다    어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성   .. 2024. 8. 3.
[백준] 1927번 최소 힙 JAVA (자바) 풀이 문제 1927번(자료구조, 우선순위 큐) :  최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오배열에 자연수 x를 넣는다 (비어있는 배열에서 시작) 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거   [입력] :  첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000) :  다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x (x 는 2³¹보다 작은 자연수 또는 0)     (x가 자연수라면 배열에 x라는 값을 추가, 0이라면 배열에서 가장 작은 값을 출력하고 제거)  [출력] :  입력에서 0이 주어진 횟수만큼 답을 출력 (만약 배열이 비어 있는 경우 0을 출력)    [설명] 힙은 우선순위 큐와 원리가 비슷해 우선순위 큐로 구현할 수 있다  우선순위 큐의 정렬 기.. 2024. 8. 2.
[백준] 13023번 ABCDE JAVA (자바) 풀이 문제 13023번 (dfs, 백트래킹)  : 총 N명이 참가   사람들은 0번 ~ N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구A는 B와 친구B는 C와 친구C는 D와 친구D는 E와 친구위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성   [입력] :  첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000), 친구 관계의 수 M (1 ≤ M ≤ 2000) :  둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻 (0 ≤ a, b ≤ N-1, a ≠ b)    (같은 친구 관계가 두 번 이상 주어지는 경우는 없다)   [출력]  :  문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력   [과정]  탐색하자 → 브루트포스 / dfs → .. 2024. 8. 2.
[백준] 1068번 트리 JAVA (자바) 풀이 문제 1068번 (dfs)  :  리프 노드 = 자식의 개수가 0인 노드    노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거     남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성   예) 리프 노드의 개수는 3개  이때, 1번을 지우면, 다음과 같이 변한다. 회색으로 색칠된 노드가 트리에서 제거 이제 리프 노드의 개수는 1개   [입력] :  첫째 줄에 트리의 노드의 개수 N (N은 50보다 작거나 같은 자연수) :  둘째 줄에는 0번 ~ N-1번 노드까지 각 노드의 부모가 주어진다    (만약 부모가 없다면 -1) :  셋째 줄에는 지울 노드의 번호    [출력] :  첫째 줄에 주어진 노드를 지웠을 때, 남은 리프 노드의 개수를 출력    [과정]  탐색하자 → 브루트포스 / .. 2024. 8. 1.
[백준] 1931번 회의실 배정 JAVA (자바) 풀이 문제 1931(그리디, 정렬) :  한 개의 회의실, N개의 회의, 회의실 사용표 :  각 회의 I에 대해 시작시간과 끝나는 시간    각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 찾기  :  회의는 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의 시작    (회의의 시작시간과 끝나는 시간이 같다면 시작하자마자 끝나는 회의)  [입력] :  첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000) :  둘째 줄부터 N+1 줄까지 각 회의의 시작시간과 끝나는 시간    (시작 시간과 끝나는 시간은 2³¹-1보다 작거나 같은 자연수 또는 0)    [출력] :  첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력    [문제접근]  1. 정렬 이용하.. 2024. 7. 17.
[백준] 2636번 치즈 JAVA (자바) 풀이 문제 2636(BFS)  : 회색으로 표시된 부분 = 치즈   X친 부분 = 판의 가장자리 (치즈 없음)   ‘c’로 표시된 부분만 한 시간 후에 녹고 빈칸과 접촉하는 치즈는 c 표시 해준다   단 치즈로 둘러쌓여있는 빈칸은 접촉해도 c표시 없어도 된다 :  치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각 개수 구해라  [입력] :  첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수 (길이는 최대 100)    판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지    (치즈가 없는 칸은 0, 치즈가 있는 칸은 1)     [출력] :  첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력 :  둘째 줄에는 모두 녹기 한 시간.. 2024. 7. 13.
[백준] 3055번 탈출 JAVA (자바) 풀이 문제 3055(BFS)  :  티떱숲의 지도는 R행 C열로 이루어져 있다    비어있는 곳은 .    물이 차있는 지역은 *    돌은 X    비버의 굴은 D    고슴도치의 위치 S  :  매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동가능    물도 매 분마다 인접한 비어있는 칸으로 확장    물과 고슴도치는 돌을 통과할 수 없다    고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다  :  고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램    (다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다)  [입력] :  첫째 줄에 50보다 작거나 같은 자연수 R과 C :  다음 R개 줄에는 티떱숲의 지도 .. 2024. 7. 12.
[백준] 9019번 DSLR JAVA (자바) 풀이 문제 9019(BFS)  :  네 개의 명령어 D, S, L, R    계산기에는 레지스터 = 0 이상 10,000 미만의 십진수 저장 가능     예) 레지스터에 저장된 n (n의 네 자릿수를 d1, d2, d3, d4)          즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)D = n x 2 (결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지)S = n - 1 (n이 0 이라면 9999 가 대신 레지스터에 저장)L = n의 각 자릿수를 왼편으로 회전 (d2, d3, d4, d1)R = n의 각 자릿수를 오른편으로 회전 (d4, d1, d2, d3) :  A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램  [입력] :  첫 줄에 T 개의.. 2024. 7. 11.

티스토리툴바