본문 바로가기

Algorithm/DFS,BFS

 (10)
DFS/BFS 다시풀기(JAVA) 연결요소의 개수 촌수계산 나이트의 이동 유기농배추 토마토 상범빌딩 적록색약 안전영역 스타트링크 숨바꼭질 1. 연결요소의 개수 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 import java.util.ArrayList; import java.util.Scanner; public class Main { private static ArrayList[] edge; private static boolean[] visited; static void dfs(int x){ visited[x] = true; for(int i..
BFS 문제 분석-2(촌수계산) 1. 촌수계산 문제 분석(boj.kr/2644)이 문제도 사실 미로찾기 문제와 다를게 없다. 방문체크를 노드기준으로 한다는 것과 다르게. 입력된 상태를 노드로 표현하면 다음과 같다. 이제 BFS를 해야한다. 시작하는 위치는 두 사람의 어느곳이든 상관없다. 나는 7에서 시작한다고 가정하겠다.그렇다면, BFS(7)로 탐색이 시작된다.미로탐색에서 쓰였던 방법처럼, 현재 노드까지의 최단경로에서 +1을 다음노드에 해준다. 7과 연결된 노드는 2와 8이다. 결과적으로 1+1이 된다. 7과 연결된 노드가 모두 방문되면, 다음 노드(q.front())를 꺼내서 연결된 노드를 방문한다. 2와 연결된 노드는 1, 7, 8, 9이다. 하지만 7은 방문되었으므로, 생각치 않는다. 1, 8 ,9의 방문체크를 2+1로 해준다. ..
BFS 문제 분석-1(미로탐색) 1. 미로탐색 문제 분석(boj.kr/2178) 이번 문제는 사실 크게 어렵지 않다. 간단한 방법으로 풀 수 있다. 우선, edge는 미로에서 이동할 수 있는 루트를 2차원 배열로 만들어야 한다. visited를 2차원 배열로 만들어야 한다. 우리가 DFS에서 했던 어떤 문제는 1차원 배열의 형태로 만들었다. 그 이유는, 각 노드에 대한 방문이다. 하지만 여기서는, 각 노드에 대해서 방문하는게 아니라, 배열의 위치를 방문하는 것이다.우리는 (1,1)에서 최종 목표로 갈 수 있는 최소 칸수를 구해야 한다. 그래서 탐색을 (1.1)에서 시작한다.화살표의 의미는, 이 바로 다음에 설명하도록 하겠다.아, 너무 당연하지만 0이면 방문하지않음, 0이 아니면 방문했음을 표현했다.현재 상태는, (1,1)에서 방문을 시..
너비 우선 탐색(breadth-first search: BFS) 자, 이제 빨리 DFS의 반대 개념인 BFS에 대해 배워보죠.BFS는 너비 우선 탐색(breadth-first search)의 약자고, 역시 컴포넌트의 모든 정점을 한 번씩 순회하는 용도입니다.DFS와 대립되는 성질을 갖고 있으며, 사용되는 곳도 매우 다릅니다.그러나 DFS와 겹치는 용도가 있는데, BFS 역시 컴포넌트의 개수를 세거나 각 컴포넌트의 크기를 구하는 데는 사용 가능합니다. DFS가 깊이를 중시했던 것에 반해 BFS는 넓이를 중시한다는데요.DFS는 한 우물만 계속 파다가 끝을 보고 나서야 다른 곳으로 옮기는 데 반해, BFS는 모든 곳을 똑같이 조금씩 조금씩 팝니다. 저번과 동일한 그래프를 예로 들어봅시다.맨 처음에 0번 정점부터 방문을 시작했을 때, 그 다음 단계에는 DFS에서와는 다르게,..
DFS 문제 분석-4(텀 프로젝트 boj_9466) 1. 텀 프로젝트 문제 분석(boj.kr/9466)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include using namespace std; #define MAX_SIZE 100001 int N, edge[MAX_SIZE], cnt;bool visited[MAX_SIZE], finished[MAX_SIZE]; /*다음에 방문할 정점을 방문한 적 있는데, DFS가 끝나지 않는다면(사이클), 다음에 방문 할 정점부터, 나한테 돌아올때까지 더한다.그리고 마지막에 나를 포함하기 위해서 cnt++을 해준다.*/ void dfs(int cur) { visited[c..
DFS 문제 분석-4(안전영역 boj_2468) 1. 안전영역 문제 분석(boj.kr/2468)이 문제는 처음에 낚였다. 왜 height=0, height=maxH일때를 왜 생각하는 건가?솔직히 아직도 잘 모르겠다. 높이가 최대이면, 다 잠겨버리는거 아닌가? 그래서 고려할 가치가 없다고 생각했다.하지만, 높이가 0일때는 구분해야한다. 왜냐면, 전부 높이가 1인 경우가 있기 때문이다.약간 문제의 낚시라고 해야하나 문제 자체는 쉬웠는데, 저 부분에서 좀 애먹었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #define MAX_SIZE 101 int row[4..
DFS 문제 분석-3(영역구하기, 음식물 피하기) 1. 영역구하기 문제 분석(boj.kr/2583) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include #define MAX_SIZE 101 int paper[MAX_SIZE][MAX_SIZE];int M, N, K;int row[4] = { -1,0,1,0 };int col[4] = { 0,-1,0,1 };int area[MAX_SIZE];int Area_cnt, djtArea; int checkRangeOver(int i,..
DFS 문제 분석-2(적록색약, 연결 요소) Bool을 이용해서 방문체크 하기 1. 적록색약 문제 분석(boj.kr/10026) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899#include //#include memset을 이용할 수 있다.#define MAX_SIZE 101#define TRUE 1#define FALSE 0 char painting[MAX_SIZE][MAX_SIZE];int bool_visit[MAX_SIZE][MAX_SIZE];int N;..

티스토리툴바