반응형 알고리즘/백트래킹10 백준 2580번 : 스도쿠 java 이 문제는 스도쿠 문제를 백트래킹을 이용하여 푸는 문제입니다. 위와 같은 스도쿠 판이 있다고 가정하겠습니다. 이 스도쿠 판에서 빈칸들을 채우기 위해서는 아래와 같이 가로, 세로, 박스 안을 확인해야 합니다. 이 세 영역에 빈칸에 넣는 수와 같은 수가 존재하지 않아야 빈칸에 수를 삽입할 수 있습니다. 코드를 보면서 이 문제의 풀이에 대해 더 자세히 설명드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int[][] board; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputSt.. 2022. 6. 23. 백준 15655번 : N과 M (6) java 이 문제는 입력 받은 배열을 정렬한 후 자신 이후의 인덱스에 있는 자료들을 M개 만큼 출력하는 문제입니다. 이 문제를 해결하기 위해서는 재귀적으로 함수를 불러오면서 불러온 횟수가 M번이 되면 출력하면 됩니다. 코드를 보시면 쉽게 이해하실 수 있으실 겁니다. import java.io.*; import java.util.*; public class Main { static int N, M; static int[] data; static int[] answer; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String.. 2022. 6. 22. 백준 15666번 : N과 M (12) java 이 문제는 입력된 값들을 저장하여 중복되는 수열이 출력되지 않게 비내림차순으로 출력하는 문제입니다. 이 문제를 풀 때 입력값이 중복된 값이 올 수 있다는 것을 유의해야 합니다. 따라서 저는 HashSet을 이용하여 중복된 값들을 저장하지 않고 중복되지 않은 값들로만 배열을 만들었습니다. 그 배열로 조건과 같이 출력하게 하여 문제를 해결하였습니다. 코드를 바로 보여드리도록하겠습니다. import java.io.*; import java.util.*; public class Main { static int M; static Integer[] intArr; static int[] answer; public static void main(String[] args) throws IOException{ Buffer.. 2022. 6. 12. 백준 1759번 : 암호 만들기 java 이 문제는 데이터를 입력받은 후 dfs를 이용하여 중복된 값이 나오지 않게 탐색하는 알고리즘입니다. 이 문제를 풀 때 조심해야하는 점은 모음이 1개 이상, 자음이 2개 이상 들어가야 한다는 조건입니다. 문자들을 입력받은 후 정렬하여 dfs를 실행하며 모음이 1개 이상, 자음이 2개 이상 들어 있는지 확인하면 되는 문제입니다. 바로 코드를 보여드리도록 하겠습니다. import java.util.*; import java.io.*; public class Main { static char[] charArr; static int L, C; static char[] answer; static boolean[] visited; public static void main(String[] args) throws IO.. 2022. 6. 11. 백준 15657번 : N과 M (8) java 이 문제는 입력을 받은 후 정렬하고 dfs를 이용하여 조건에 맞게 출력하는 문제입니다. 예제 2번을 예시로 그림을 통해 이 문제를 설명해드리도록 하겠습니다. 위의 그림은 예제 2번에 맞게 N크기의 배열과 M 크기의 배열을 만들었습니다. M 배열에 들어있는 자료들이 출력될 값입니다. 위 그림과 같이 M배열의 첫 번째에 들어갈 자료는 초록색 박스로 두 번째에 들어갈 자료는 빨간색 박스로 표시하였습니다. 이제 출력이 어떻게 되는지 계속해서 보여드리겠습니다. 초록색 박스가 N배열의 첫번째 칸을 가리킬 때는 이렇게 진행이 됩니다. 이제 초록색 박스를 N배열의 두 번째 칸으로 옮겨보겠습니다. 그럼 위의 그림과 같이 초록색 박스가 시작되는 지점부터 빨간색 박스도 시작합니다. 계속 진행시켜보도록 하겠습니다. 초록색 박.. 2022. 6. 10. 백준 15663번 : N과 M (9) java 이 문제는 dfs를 이용한 백트래킹 문제입니다. 이 문제를 풀 때 유의해야 하는 것은 중복되는 입력이 있을 수 있고 중복되는 수열을 여러 번 출력하면 안 된다는 것입니다. 코드를 보면서 설명 드리겠습니다. import java.io.*; import java.util.*; public class Main { static int[] numArr; static int[] out; static boolean[] visited; static int M; static int N; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in));.. 2022. 6. 3. 백준 15654번 : N과 M(5) java 이 문제는 재귀를 이용하여 원하는 조건을 출력하는 백트래킹 문제입니다. 이 문제를 풀 때 Arrays.sort를 이용하여 입력받은 배열들을 오름차순으로 정렬한 후에 푸시면 됩니다. 바로 코드를 보여드리겠습니다. import java.io.*; import java.util.*; public class Main{ static int[] intArr; static int[] dfsArr; static boolean[] visited; static int N; static int M; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System... 2022. 5. 31. 백준 14889번 : 스타트와 링크 java 이 문제는 백트래킹 파트 안에 있는 깊이 우선 탐색(dfs)을 이용하여 푸는 문제입니다. 이 문제를 풀 때 유의해야 하는 점은 N이 6이라고 할 때 1 2 3이 한 팀이고 4 5 6이 한 팀일 때 1->2, 2->1로 받는 능력치 1->3, 3->1로 받는 능력치 2->3, 3->2로 받는 능력치 이렇게 안에 포함된 모든 팀원들의 능력치 합을 더해서 구해주어야 된다는 겁니다. 코드를 보면서 추가로 설명드리도록 하겠습니다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main{ static int[][].. 2022. 5. 25. 이전 1 2 다음 반응형
