백트래킹4 [9663] N-Queen , 자바 , dfs(백트래킹) 1. 문제레벨: G4알고리즘: dfs(백트래킹)풀이시간: 30분힌트 참조 유무: 유https://www.acmicpc.net/problem/96632. 문제 풀이실패 시도:서로 공격하지 않는 경우의 수로 구하려고 하였으나 N^2 C N 의 시간 복잡도가 나왔습니다. 이는 한 눈에 봐도 큰 경우의 수 입니다. 아무리 백트래킹을 한다그래도 N = 15, 시간제한 = 10초 안에 불가능할 거라 판단하였습니다.전체 경우의 수 - 서로 공격하는 경우 로 구하려고 하였으나 서로 공격하는 경우에서 2 ~ N이 서로 공격하는 경우를 구할 때 중복이 발생함으로 중복을 해결하는 과정이 너무 복잡해보였습니다. 잘못된 방법인 냄새실패 원인: N^2 C N에 대한 오해N^2 C N은 "N^2개의 칸에서 N개의 퀸을 선택하여 .. 2025. 1. 19. [백준 1799] 비숍 / 자바 / 백트래킹 + 분할정복 #문제레벨: G1알고리즘: 백트래킹 + 분할정복풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1799#문제 풀이완전탐색을 할 경우 2의 100승으로 무조건 시간초과입니다. 그렇다 하면 조금 더 긍정적으로 생각해보겠습니다. 흰색칸 비숍과 검정칸 비숍은 서로 영향을 줄 수 없습니다. 그래서 우린 흰색칸 비숍과 검정칸 비숍을 나누어서 탐색하게 된다면2^50 + 2^50 으로 아까보다 나아졌습니다. 그래도 우린 시간초과에 걸립니다. 그렇다면 우리에겐 dp가 남아있습니다. 위 문제를 dp로 풀 경우를 생각하면 비트마스킹 dp을 생각해볼 수 있습니다. 이차원배열을 100자리의 비트마스킹으로 표현하는 것입니다. 그러나 대각선의 겹치는 비숍이 있는지 검사하기에는 까다로울 .. 2025. 1. 18. [백준 2239] 스도쿠 / 자바 / dfs(백트래킹) #문제 레벨: G4 알고리즘: dfs(백트래킹)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2239#문제 풀이 해당 자리에 숫자를 놓으려면 해당 열, 해당 행, 해당 박스 안에 같은 숫자가 있으면 안된다. 이것들을 검사하는 코드를 구현하고 백트래킹을 통해서 숫자를 채워넣으면 된다.dfs 코드는 아래와 같이 방문한다. -------------------------> 1 번째 행-------------------------> 2 번째 행 -------------------------> 3 번째 행 -------------------------> 4 번째 행 -------------------.. 2024. 9. 1. [백준 1987] 알파벳 / 자바 / 백트래킹 문제 레벨: G4알고리즘: 백트래킹풀이시간: 30분힌트 참조 유무: 무https://www.acmicpc.net/problem/19871 번째 시도 백트래킹 기본적인 문제굳이 설명을 적지 않겠다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;public class Main { static int ans = Integer.MIN_VALUE; static boolean[][] visited; static int[] dx = {1,0,0,-1}; static int[].. 2024. 6. 19. 이전 1 다음
