본문 바로가기

전체 글

 (35)
너비 우선 탐색(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,..
Heap 구현-C 1. Heap.h 12345678910111213141516171819202122232425262728293031323334353637383940414243#ifndef HEAP_H#define HEAP_H #include #define TRUE 1#define FALSE 0 #define HEAP_LEN 100 typedef char HData;typedef int Priority; typedef struct _heapElem { Priority pr; HData data;}HeapElem; typedef int PriorityComp(HData d1, HData d2); typedef struct _heap { PriorityComp* comp; int numOfData; HData heapArr[H..
이진트리(Binary_Tree) 구현-C 1. BTree.h : 이진트리 자료구조의 헤더파일, ADT1234567891011121314151617181920212223242526272829303132#ifndef BTREE_H#define BTREE_H #include #include typedef int BTData; typedef struct _BTreeNode{ BTData data; struct _BTreeNode* left; struct _BTreeNode* right;}BTreeNode; typedef void visitFunPtr(BTData data); BTreeNode* makeBTreeNode(void);//노드를 만들고 연결하지는 않음.BTData getData(BTreeNode* bt);//bt의 데이터를 return.vo..
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;..
알고리즘 문제 input입력 귀찮을때... 알고리즘 문제 풀이할때, 입력이 상당히 귀찮다. 이를 해결해보자. Visual Studio 2015에서 프로젝트를 만들고 속성페이지에 들어가서 명령인수를 input.txt 라고 설정한다(다르게 설정해도 상관없다.)그리고 해당 프로젝트의 소스파일 안에 input.txt를 만든다. 마지막으로, input.txt에 input할 데이터들을 입력한다. 그러면 자동으로 입력이 된다.

티스토리툴바