Baekjoon/[6] 백트래킹12 [백준] 9663번 N-Queen JAVA (자바) 풀이 문제 9663번 (백트래킹) : N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제 N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램 [입력] : 첫째 줄에 N이 주어진다. (1 ≤ N [출력] : 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력 [과정] 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 pos메서드를 통해 참이 아니라면 다시 바꿔서 탐색한다 참이면 더 깊이 들어간다 종료 조건) depth==N 모두 종료되는 것이 아니라 N의 퀸을 세웠으면 경우의 수 1개를 카운트한다 1. 퀸의 공격 방향은 대각선, 세로, 가로같은 행, 같은 열, 같은 대각선은 피해야한다하나의 행씩.. 2024. 8. 6. [백준] 1987번 알파벳 JAVA (자바) 풀이 문제 1967번 (백트래킹) : 세로 R칸, 가로 C칸으로 된 표 모양의 보드 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다 말은 상하좌우로 이동 가능 새로 이동한 칸의 알파벳 ≠ 지금까지 지나온 모든 칸에 적혀 있는 알파벳 (즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다) 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구해라 (좌측 상단의 칸 포함) [입력] : 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다 (1 ≤ R,C ≤ 20) : 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳 [출력] : 첫째 줄에 트리의 지름을 출력 [과정] 탐색하자 → 브루트.. 2024. 8. 6. [백준] 15686번 치킨 배달 JAVA (자바) 풀이 문제 15686번 (백트래킹, 브루트포스) : 크기가 N×N인 도시 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나 : 사람들은 "치킨 거리"라는 말을 주로 사용 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리 각각의 집은 치킨 거리를 가지고 있고 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 거리는 |r1-r2| + |c1-c2|로 구한다 : 0은 빈 칸, 1은 집, 2는 치킨집 이 도시에 있는 치킨집은 모두 같은 프랜차이즈이며 일부 치킨집을 폐업시키려고 한다 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개 나머지 치킨집은 모두 폐업시켜야 한다 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성 .. 2024. 8. 3. [백준] 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. [백준] 15652번 N과 M(4) JAVA (자바) 풀이 문제 15652번 (백트래킹) : 1부터 N까지 자연수 중에서 M개를 고른 수열 (중복선택 가능) : 고른 수열은 비내림차순비내림차순 : A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK (예) N = 3, M = 2 인 경우 1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다 1, 1 / 1, 2 / 1, 3 / 2, 2 / 2, 3 이렇게 만든 수열을 한줄에 하나씩 출력한다 [입력] : 첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8) [출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X) 수열의 원소는 공백으로 구분해서 출력 : 수열은 사전 순으로 증가하는 순서로 출력 [과정] 탐색하자 → 브루트포스 / dfs →.. 2024. 5. 4. [백준] 15650번 N과 M(2) JAVA (자바) 풀이 문제 15650번 (백트래킹) : 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 골라서 수열 구하기 : 고른 수열은 오름차순 (예) N = 3, M = 2 인 경우 1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다 1, 2 / 1, 3 / 2, 3 이렇게 만든 수열을 한줄에 하나씩 출력한다 [입력] : 첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8) [출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X) 수열의 원소는 공백으로 구분해서 출력 : 수열은 사전 순으로 증가하는 순서로 출력 [과정] 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 문제 조건 .. 2024. 5. 3. [백준] 5568번 카드 놓기 JAVA (자바) 풀이 문제 5568 (백트래킹) : 카드 n장 (4 ≤ n ≤ 10) 각 카드 1이상 99이하의 정수 : 카드 k장 (2 ≤ k ≤ 4) 선택 후 가로로 나란히 정수를 만들기 : 만들 수 있는 정수는 모두 몇 가지일까? [입력] : 첫째 줄에 n, 둘째 줄에 k: 셋째 줄 ~ n개 줄에는 카드에 적혀있는 수 [출력] : 만들 수 있는 카드 개수 [과정] 조합 중복 방지 vs 결과 중복 방지조합 중복 (백트래킹으로 해결)조합 중복 방지란 (1,1)이 아닌 (1,2)처럼 서로 다른 조합을 말한다 결과 중복 (hashset으로 해결)결과 중복 방지란 (1,2)와 (2,1)을 같은 값으로 처리하는 것을 말한다 [코드]import java.io.*;import java.util.*;public class.. 2024. 5. 3. 이전 1 2 다음