본문 바로가기

dfs34

[백준] 1987번 알파벳 JAVA (자바) 풀이 문제 1967번 (백트래킹)  :  세로 R칸, 가로 C칸으로 된 표 모양의 보드    각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다    말은 상하좌우로 이동 가능    새로 이동한 칸의 알파벳 ≠ 지금까지 지나온 모든 칸에 적혀 있는 알파벳    (즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다)    좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구해라 (좌측 상단의 칸 포함)   [입력] :  첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다 (1 ≤ R,C ≤ 20)  :  둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳   [출력] :  첫째 줄에 트리의 지름을 출력   [과정]  탐색하자 → 브루트.. 2024. 8. 6.
[백준] 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.
[백준] 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.
[백준] 10819번 차이를 최대로 JAVA (자바) 풀이 문제 10819번 (브루트포스, 백트래킹)  :  N개의 정수로 이루어진 배열 A    배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구해라 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|   [입력] :  첫째 줄에 N (3 ≤ N ≤ 8) :  둘째 줄에는 배열 A에 들어있는 정수 ( -100 ≤ 정수 ≤ 100 )   [출력] :  식의 최댓값을 출력    [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  수열을 모두 바꿔가며 max 값을 찾기 때문에 브루트포스가 맞다  종료 조건) depth==N N개의 숫자를 모두 뽑았기 때문에 종료하고 sum 계산 후 result로 max값 뽑아내기  1. 계산은 i.. 2024. 6. 26.
[백준] 2529번 부등호 JAVA (자바) 풀이 문제 2529번 (백트래킹)  :  부등호 기호 ‘’가 k개 나열된 순서열 A가 있다    부등호 기호 앞 뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다    숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다  :  부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있다    부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다   [입력] :  첫 줄에 부등호 문자의 개수 정수 k :  그 다음 줄에는 k개의 부등호 기호 (k의 범위는 2 ≤ k ≤ 9)    [출력] :  k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력 (첫 자리가 0인 경우도 정수에 포함)   [과정]  탐색하자 → 브루트.. 2024. 6. 25.
[백준] 10971번 외판원 순회2 JAVA (자바) 풀이 문제 10971번 (백트래킹)  :  1번 ~ N번 도시    한 도시에서 출발해 N개의 도시를 거쳐 원래의 도시로 돌아오는 순회 여행 경로    (한 번 갔던 도시로는 다시 갈 수 없다)  :  이동 비용 W[i][j] = 도시 i에서 도시 j로 가기 위한 비용 (W[i][j] ≠ W[j][i])    W[i][i]는 항상 0 / 갈 수 없는 경우도 0  :  가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.   [입력] :  첫째 줄에 도시의 수 N (2 ≤ N ≤ 10) :  다음 N개의 줄에는 비용 행렬 (각 행렬의 성분은 1,000,000 이하의 양의 정수)    (갈 수 없는 경우는 0) [출력] :  순회에 필요한 최소 비용을 출력    [과정]  탐색하자 .. 2024. 6. 22.
[백준] 10974번 모든 순열 JAVA (자바) 풀이 문제 10974번 (백트래킹)  :  1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성   [입력] :  첫째 줄에 N(1 ≤ N ≤ 8)  [출력] :   첫째 줄부터 N개의 줄에 걸쳐서 모든 순열을 사전순으로 출력   [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹   문제 조건 1) 숫자 중복금지  문제 조건 2) 수열 원소 오름차순   종료 조건) 배열이 M만큼 채워지면 출력하고 boolean false  N과 M(1) 문제와 비슷하다 방문기록을 체크해가며 숫자를 추가한다   [코드]import java.io.*;import java.util.*;public class Main{ static int N,arr[]; static boolea.. 2024. 5. 27.
[백준] 6603번 로또 JAVA (자바) 풀이 문제 6603번 (백트래킹)  :  {1, 2, ..., 49}에서 6개 택  :  k개(k>6) 골라 집합 S 만들어 6개의 조합 만들기   [입력] :  각 줄의 첫 번째 수는 k (6     (입력 마지막 줄 = 0)  [출력] :  각 테스트 케이스마다 경우의 수 출력 (사전 순 / 중복 금지)  :  각 테스트 케이스 사이에는 빈 줄 출력   [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  문제 조건 1) 숫자 중복금지  문제 조건 2) 수열 원소 오름차순   종료 조건) 배열이 M만큼 채워지면 출력하고 boolean false  N과 M(2) 문제 응용버전이다  마찬가지로 boolean이 필요없다 현재 숫자보다 무조건 다음 인덱스의 숫자가 커져야 하기 때문에  굳이 .. 2024. 5. 4.

티스토리툴바