dfs45 백준 14248 자바 - 점프 점프 (BOJ 14248 JAVA) 문제 : boj14248 문제 자체의 정의에 따라 i번째 정점에서 i-Ai, i+Ai 로의 간선이 생긴다. 이에 대해 단순히 방문 가능한 위치만 찾으면 되므로 dfs 혹은 bfs로 더이상 진행 불가할때까지 진행해보면서 방문한 곳의 개수를 세면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { boolean[] v; int cnt = 0, n; int[] arr; private void dfs(int s) { if (sn||v[s]) return; v[s] = true; cnt++; dfs(s+arr[s]); dfs(.. 2022. 1. 11. 백준 2636 자바 - 치즈 (BOJ 2636 JAVA) 문제 : boj2636 1. 우선 '치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다.' 부분부터 생각해보자. 1로 막혀있는 0 부분은 공기로 치지 않는다는 의미로, 이 조건에 따라 단순히 '0'과 인접한 '1'만 찾아선 안된다. 탐색에 익숙하지 않다면 아이디어를 떠올리기 힘들 수 있다. 이 문제의 경우 외부 공기에서부터 탐색을 시작하면 치즈로 둘러쌓인 내부는 보지 않을 수 있다. 그리고 이 문제는 친절하게 판의 가장자리에는 치즈가 놓여있지 않다고 한다. 그러니 단순하게 0,0 지점에서 시작하면 언제나 외부 공기에서 시작함을 보장할 수 있다. 따라서 모든 치즈가 사라질 때 까지, 0,0 부터 시작하는 bfs 혹은 dfs를 계속 반복하고, 그때마.. 2021. 12. 18. 백준 1068 자바 - 트리 (BOJ 1068 JAVA) 문제 : https://www.acmicpc.net/problem/1068 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1068.java 제거된 1개가 루트노드일 경우 무조건 0을 출력하면 된다. 그렇지 않다면, 루트노드부터 탐색할 때 제거된 노드쪽으로는 탐색을 진행하지 않으면서 리프노드들의 갯수를 세주면 된다. 로직은 1. 부모 -> 자식으로 단방향 그래프 간선 정보를 저장해둔다. 2. 루트노드부터 갈 수 있는 모든 곳을 탐색하며. 이 때 제거된 노드로는 진입하지 않는다. 3. 탐색 중 리프노드를 발견하면 카운팅한다. 2021. 11. 9. 백준 3409 자바 - 문자 방정식 (BOJ 3409 JAVA) 문제 : https://www.acmicpc.net/problem/3409 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/03400/BOJ_3409.java 첫 다이아 티어 성공한 문제이다. 사실 골드나 플래도 제대로 못풀다보니 다이아급은 쳐다도 안봤었는데 얼마나 어려운지 볼려고 도전해봤다(보통 티어랑 알고리즘 분류는 끄고푸는데, 문제 검색을 실버, 골드, 플래 전체 체크하고 순서 랜덤으로 두고 검색해서 푸는 편임). 결과는 의외로 쉬웠다. 안쫄고 이제 다야도 한번 덤벼봐야겠다. 풀고보니 다른 분들은 DP(다이나믹 프로그래밍)으로 다들 분류를 설정해뒀던데 내 경우엔 그냥 dfs로 풀었다. 이 문제의 경우 문제만 놓고 보면 복잡해보일.. 2021. 10. 28. 백준 1412 자바 - 일방통행 (BOJ 1412 JAVA) 문제 : https://www.acmicpc.net/problem/1412 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01400/BOJ_1412.java 플래 중위권 문제치곤 그리 어렵지 않았다. 구현이 어렵다기보다는 아이디어를 떠올리기 좀 어려울 수 있는 문제라 티어가 높게 책정된 듯 하다. 일단 '도시 x에서 출발해서 다시 그 도시 x로 돌아올 수 없게 만드는 것이다.' 부분을 만족하려면, 결국 자기 자신으로 되돌아오는 Cycle이 없으면 된다. 여기까진 쉽게 생각할 수 있는데 그럼 양방통행와 일방통행 도로의 두 종류가 있는 상황에서 어떻게 해야 Cycle을 없앨 수 있는지가 관건이다. 그래서 일단 그려보며 열심히 생각해봤는.. 2021. 10. 11. 이전 1 2 3 4 5 다음
