본문 바로가기

알고리즘/DFS33

[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.
[백준 17090] 미로 탈출 / 자바 / dfs(dfs 코드구현 연습) #문제         레벨: G5알고리즘:  dfs(dfs 코드구현 연습)풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/17090#문제 풀이        visted이 0,1,2(방문x,       방문O && 정답아님,     방문O && 정답임) 세가지 상태를 담을 때import java.util.*;public class Main { static int N, M; static char[][] maze; static int[][] visited; static int[] dx = {-1, 0, 1, 0}; // U, R, D, L static int[] dy = {0, 1, 0, -1}; // U, R, D, L public stat.. 2024. 8. 16.
[백준 1240] 노드사이의 거리 / 자바 / dfs (dfs구현연습) #문제         레벨: G5알고리즘:  dfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/1240#문제 풀이         dfs + void  static void dfs(int current, int end, int distance) { if (current == end) { result = distance; return; } visited[current] = true; for (int[] next : tree[current]) { if (!visited[next[0]]) { dfs(next[0], end, dista.. 2024. 8. 16.
[백준 18251] 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) / 자바 / dfs + 카데인 알고리즘 #문제         레벨: P4알고리즘: dfs + 카데인 알고리즘풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/18251#문제 풀이        문제 풀기에 앞서 카데인 알고리즘을 알고가야 한다.  카데인 알고리즘이란  최대 부분 합 수열을 구할 때 사용한다. 평소 이 알고리즘 이름은 안적도 없지만, 이러한 방식으로 문제를 푼 경우가 있을 것이다. 이거에 이름을 붙여 더 확실히 기억해보자.예시 배열: [-2, 1, -3, 4, -1, 2, 1, -5, 4]localMaxValue: 현재 위치까지의 연속된 부분 배열의 최대 합 globalMaxValue: 지금까지 발견된 전체 최대 부분 배열의 합초기 상태: [-2, 1, -3, 4, -1, 2,.. 2024. 8. 12.
[백준 11400] 단절선 / 자바 / dfs ** #문제         레벨: P4알고리즘: dfs풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/11400#문제 풀이        가장 쉬운 방법은 모든 단절선을 끊어보고 dfs 여러번을 통해 트리의 개수가 2개이상인지 세어보는 것이다. 그러나 입력제한을 보면 시간초과가 날 것을 직감할 수 있다.문제의 해결법은 노드를 처음 발견했을 때의 순서와 만남의 가중치를 이용해 푸는 것이다. 처음 방문한 노드라면 처음 발견했을 때의 변수와 만남의 가중치에 발견한 순서를 부여해준다. 만약 처음 방문한 게 아니라면  1를 시작으로 탐색했을 때 1 -> 4 -> 5  -> 6(1에 의해) -> 7 -> 2 -> 3이렇게 정점을 탐색하는 것이다. 근데 우리가 중요한 건 간선을 .. 2024. 8. 12.
[백준 15681] 트리와 쿼리 / 자바 / dfs #문제         레벨: G5알고리즘: dfs 풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/15681#문제 풀이         가장 직관적인 건 Q를 새로 입력 받을 때마다 세팅해놓은 트리의 자식 개수를 탐색하는 거다. 아래코드와 같이 말이다. 그러나 아래와 같이 하면 시간초과가 난다.import java.io.*;import java.util.*;public class Main { static List> tree; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syste.. 2024. 8. 12.
[백준 1103] 게임 / 자바 / dfs + dp #문제         레벨: G2알고리즘: dfs + dp풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/1103#문제 풀이         dfs+dp 코드 구현은 워낙 다양하다. 그래서 자기에게 맞는 코드를 찾아야 한다. 자기가 이해하기 쉬운 코드를 짜야한다. visited배열이 언제 true,false가 되고 dp 값이 어떻게 언제 채워지는지 정확히 이해해야 한다.아래 코드는 한 번씩 이동할 때마다 dp배열에 +1씩 새긴다. 만약 dp 배열에 값이 지금 새겨넣으려는 값보다 큰 경우 그 경로에서는 탐색을 멈춘다. 왜냐하면 이미 이전에 깊이 탐색했다는 뜻으로. vsited배열은 무한루프를 탐색하기 위함이기 때문에 다른경로에 영향을 주면 안된다. 한 경로에서 .. 2024. 8. 3.

티스토리툴바