본문 바로가기

BFS68

백준 1707 자바 - 이분 그래프 (BOJ 1707 JAVA) 문제 : boj1707 '그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.' 무슨말이냐면, 정점을 두개의 그룹으로 나눴을 때, 해당 그룹끼리는 간선이 없도록 나눌 수 있으면 이분 그래프라는 얘기이다. 아래의 그림을 보면 바로 이해가 될 것이다. 1,2,3은 이분 그래프를 그려봤다. 4는 이분 그래프가 아닌 경우이다. 즉, 어떻게든 2 종류의 정점으로 나눌 때 간선 연결된 것 끼리 같은 종류만 아니면 된다 (4번의 경우 노란 정점 둘이 간선이 연결되었으므로 이분 그래프가 아니다. 그리고 다른 방식으로 2종류로 나눠도 모두 마찬가지로 이분 그래프가 될 수 없다.). 또 .. 2022. 3. 22.
백준 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.
백준 8598 자바 - Zając (BOJ 8598 JAVA) 문제 : https://www.acmicpc.net/problem/8598 일단은 무지성으로 BFS 돌리면 되는 문제긴 하다. 그래서 딱히 안적을까 했는데, 언어가 이상하다보니 번역기 돌려도 놓칠만한 부분 적어봄. 'x'는 못감. 'z'가 시작점. 'n'이 도착지점. 다만 문제 특성상 n에서 출발해서 z에 도착해도 상관은 없다. 그리고 제일 중요한 부분은 길이 존재하지 않을 경우 "NIE"를 출력해야 한다. 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/08500/BOJ_8598.java import java.io.DataInputStream; import java.io.IOException; import java.sql.Array.. 2021. 11. 23.
백준 16509 자바 - 장군 (BOJ 16509 JAVA) 문제 : https://www.acmicpc.net/problem/16509 기본 BFS 문제다(구현이 상당히 귀찮은). 좀 덜 귀찮으려면 다음과 같이 하면 된다. 1. BFS 이동 위치를 문제에서 제시된 이동 위치 끝 지점만으로 한다. (코드의 dr, dc) 2. 이동하면서 장군에 걸리는 지점의 경우 이동이 불가하므로, 이 부분에 대한 체크 중 첫번째로 '상'의 상하좌우에 위치한 부분을 체크한다. (코드의 'switch (d)' 부분) 3. 다음으로 나머지 이동구간에 있는 지점들은, '1'에서 지정한 위치에서 대각선으로 한칸 이동한 위치이다. (코드의 'if (cr+dr[d]+(dr[d] 2021. 11. 18.
백준 17394 자바 - 핑거 스냅 (BOJ 17394 JAVA) 문제 : https://www.acmicpc.net/problem/17394 일단 A와 B 사이의 소수라는 조건이 없다고 생각해보자. 이 경우 1차원 좌표평면 상에서 시작점으로 부터 1. 현재위치/2 2. 현재위치/3 3. 현재위치-1 4. 현재위치+1 으로 이동하는 BFS 문제라 볼 수 있다. 그럼 이제 A, B 사이의 소수를 도착점으로 하는 방법만 찾으면 된다. B의 최대값은 100000이므로, 100000까지의 모든 소수만 찾으면 된다. 이 때, 당연하게도 매번 소수판정을 하면 시간초과가 날 것이다. 그러니 TC들 진행하기 이전에, 100000까지의 모든 소수를 찾아두면 된다. 이 경우 에라토스테네스의 체 방식으로 구해두면 편하게 소수를 구할 수 있다. 이 때 100000의 square root 까.. 2021. 11. 17.
백준 14217 자바 - 그래프 탐색 (BOJ 14217 JAVA) 문제 : https://www.acmicpc.net/problem/14217 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/14200/BOJ_14217.java 문제 길이에 비해 사실 생각보다 쉬운 문제이다. 결국 시간복잡도가 문제인데, 가장 쉽게 생각할 수 있는 방법은 그냥 무작정 q줄에 대해 매번 해당 edge를 추가하거나 제거한 후 최단거리를 찾아보는 방식이다. 그럼 최단거리 찾기에 가장 간단한 bfs부터 보자. O(V+E) 정도이므로, O(N^2)정도고, q가 최대 500번이므로 최종적으로 최악의 경우 O(500^3) 정도로 별 문제가 없다는걸 알 수 있다. 그러니 그냥 입력 쫙~ 받고 q줄에 대해 매번 간선을 제거하거나 추.. 2021. 10. 14.
BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS (2022-08-27 업데이트) 2022-07-21 업데이트 : 글 맨 아래에 '풀어보기'로 풀어볼만한 문제 링크 추가 2022-08-27 업데이트 : '풀어보기' 좀 더 추가, 목차 추가 목차 BFS (Breadth-first Search) 명확히 검증하면서 쓴게 아니라서 틀린 부분 있으면 알려주세요! - BFS와 DFS 대충 곰처럼 생긴 섬이 바다에 떠 있다. 편의상 이 섬을 20등분해서 격자 형태로 구역을 나누었다. 이제 우측상단의 귀(곰 입장에서 왼쪽귀)부터 출발해서 섬 전체를 둘러보려 한다. 둘러보는 방법은 여러가지가 있을 수 있다. 빨간 숫자는 둘러본 순서를 뜻한다. (0 부터 19까지) A처럼 자신과 가까운 곳부터 순서대로 살펴볼수도 있다. 격자형태로 나누었으므로 Manhattan Distance (Taxicab Geome.. 2021. 9. 24.

티스토리툴바