본문 바로가기

분류 전체보기

 (36)
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,..
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;..

티스토리툴바