본문 바로가기

dfs

[BOJ] 백준 [3109] 빵집 JAVA
알고리즘,PS/백준 2022. 3. 7. [BOJ] 백준 [3109] 빵집 JAVA https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net [문제] [풀이] 왼쪽에서 오른쪽으로 파이프를 쭉 연결해야 하는데 , 최대한 많이 연결해야 한다. 그러기위해선 2가지의 조건을 생각해야한다. 1. [오른쪽위 , 오른쪽, 오른쪽아래] 순서대로 연결해야함 => 만약 y좌표가 0번째에서 출발해서 맨 오른쪽 아래에 꽂히면 다른 1~n 번째에서는 절대 연결이 불가능 2. 이 문제는 백트래킹문제가 아니라 그리디 문제이기 때문에 모든 경우를 따지면 안된다 => 종결조건에 다..
[프로그래머스] [Level3] 양과늑대 JAVA
알고리즘,PS/프로그래머스 2022. 2. 8. [프로그래머스] [Level3] 양과늑대 JAVA https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr [문제] [풀이] 처음엔 트리 DP 문제인줄 알고 접근했었다가 다시 돌아올 수 있다는 조건때문에 풀지 못했었다. 이 문제는 오히려 중복체크를 하지 않아도 되기때문에 그리디+탐색으로 충분히 풀 수 있었다. 1. 탐색..
[BOJ] 백준 [14503] 로봇 청소기 JAVA
알고리즘,PS/백준 2021. 8. 27. [BOJ] 백준 [14503] 로봇 청소기 JAVA https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 풀이 단순 DFS 시뮬레이션 문제이다. 특이한점은 dfs 안의 다른 조건으로 재귀호출을 두 번 한다는것. map[y][x] = 1 : 벽 map[y][x] = 2 : 청소 된 상태로 만들기 map[y][x] = 0 : 청소 안된 상태 문제에 나와있는 조건을 따라서 탐색한 방향 nextX,nextY 가 청소되어있는지 확인 후 움직이거나 청소가 다 되어 있거나 벽인경우 , 후진 할 수 있다면 ..
[BOJ] 백준 [1303] 전쟁 - 전투 JAVA
알고리즘,PS/백준 2021. 8. 21. [BOJ] 백준 [1303] 전쟁 - 전투 JAVA 문제 풀이 1. dfs 탐색으로 같은 문자인 경우에만 진행하도록 함2. dfs 호출될때 마다 cnt 카운트 수 1씩 증가3. 한 무더기(?) dfs 탐색 끝났을 때 , 그 진영무리의 위력값 cnt*cnt 을 합산 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 import java.util.*; import java.io.*; public class Main{ static int w,h,cnt,white,blue; static char[][] map;..
[BOJ] 백준 [14888] 연산자 끼워넣기 JAVA
알고리즘,PS/백준 2021. 8. 20. [BOJ] 백준 [14888] 연산자 끼워넣기 JAVA 문제 풀이 이 문제는 재귀적 완전탐색(DFS) + 백트래킹 문제이다.연산자를 차례대로 방문하면서 끼워넣어 완전한 식과 그에대한 total 값을 낸 다음 , 사용하였던 연산자 개수를 회복하면서 다른 순서 방식을 통해 다시 반복하는 식으로 하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 import java.util.*; import java.io.*; public class Main{ static int N; static int[] arr; st..
[BOJ] 백준 [1068] 트리 JAVA
알고리즘,PS/백준 2021. 6. 15. [BOJ] 백준 [1068] 트리 JAVA 문제 풀이 생각보다 간단한 문제이다 . 끊어질 노드를 C 라고 하자. 그래프를 ArrayList 배열로 만든 뒤 끊어질 노드'C'의 위치까지 처음부터 다 받아서 그래프를 단방향으로 연결할 때 C가 나오면 연결을 안 해주면 끝. root 부터 DFS 돌리면서 ArryList의 size가 0이면 leaf 노드이다. 입력 노드'e' 를 받을때 3가지의 경우로 나눌 수 있는데 1. e 가 root 일때 => e == -1 2. e 가 끊어질 노드 'C' 이거나 연결하려는 노드의 부모노드가 'C'일때 => ( e==C || i ==C ) 3. 그외 경우엔 단방향 연결 단방향으로 연결이 완성된 그래프를 root 부터 DFS 재귀호출을 이용하여 자식이 없는 노드를 카운트하면 끝. 이때 , 끊어질 노드 'C'가 roo..
[BOJ] 백준 [1937] 욕심쟁이 판다 JAVA
알고리즘,PS/백준 2021. 6. 14. [BOJ] 백준 [1937] 욕심쟁이 판다 JAVA 이 문제는 DFS + DP 문제이다. 여기서 DP는 최대 생존가능일 수를 기록. 기본적으로 , 입력을 map으로 받았을때, 다음 이동해야 하는 방향의 값이 지금의 값보다 더 커야한다. 즉 , map[y][x] < map[nextY][nextX] 가 성립 해야 한다. 그리고 탐색했던곳을 중복탐색하는 것을 막기위해 메모이제이션 기법으로 dp를 바로 반환해주는것이 핵심이다. 그렇지 않으면 시간초과 발생. if(dp[y][x] != 1) return dp[y][x]; dfs로 탐색했을때 , 현재 기록된 생존가능일 수 보다 더 오래 살 수 있으면 갱신. dp[y][x] = Math.max(dfs(nextX,nextY)+1,dp[y][x]); 처음에 바로 떠 올리기엔 쉽지 않은 문제이다. 12345678910111..
LIST
Recent Posts
Popular Posts
Archives
Visits
Today
Yesterday

티스토리툴바