본문 바로가기
728x90

BFS5

[programmers] Lv.2 타겟 넘버(c++) DFS, BFS 두 방법으로 풀어봤다. 더보기 #include using namespace std; int answer=0; void dfs(vector& numbers, int& target, int idx, int num){ if(idx+1 == numbers.size()+1){ if(num == target) answer++; return; } dfs(numbers, target, idx+1, num+(-1)*numbers[idx]); dfs(numbers, target, idx+1, num+numbers[idx]); } void bfs(vector& numbers, int& target){ queue que; que.push({numbers[0], 1}); que.push({(-1)*numbers.. 2022. 5. 24.
BFS (Breadth First Search, 너비 우선 탐색) 접근 graph 또는 tree를 탐색하는 알고리즘이다. 특정 노드부터 시작하여 인접한 노드들을 먼저 탐색한다. (최단 경로를 찾을 때 사용) 특정 노드로부터의 거리에 따라 순서대로 탐색한다. 알고리즘 큐(queue)와 while문을 사용한다. 큐(queue)에서 꺼낼 때, 그 노드를 visit 했다고 표시한다. 큐(queue)에서 꺼낸 노드와 인접한 노드들을 큐(queue)에 집어넣는다. 큐(queue)가 empty상태가 될 때까지 수행한다. Pseudo-code while(!queue.empty){ current = queue.pop; current.visited = true; for(current.adj) if(!adj.visited) queue.push(adj); } 적용 더보기 https://jo.. 2022. 5. 22.
[programmers] Lv.2 카카오프렌즈 컬러링북(c++) 더보기 #include #include using namespace std; vector visit; int nb_area; vector x_dir; vector y_dir; int find_area(int i, int j, vector picture){ nb_area++; queue que; que.push({i, j}); visit[i][j] = true; int cnt = 0; while(!que.empty()){ auto[x, y] = que.front(); que.pop(); cnt++; for (int k = 0; k = 0 && x + x_dir[k] = 0 && y + y_di.. 2022. 5. 6.
[programmers] Lv.4 동굴 탐험(c++) 4단계는 어려운거같다... 코드를 봐도 cycle을 의미한다하여 응? 왜 그게 cycle을 의미하는건데? 근본적인 질문이 떠오르고 내 방식대로 하려하면 왠지 너무 복잡해진다. 근데 대부분의 답은 내 방식대로 한게 맞는거같다.. 검색하다가 위상정렬(topology sort)라는 것을 알게됐다. (이 해설에 들어갔다가 알게됨 : https://2jinishappy.tistory.com/200, 풀이는 참고하지 않았고, 검색해서 찾아낸 위상 정렬을 설명해주고있는 아래 참고 링크에서 sort 원리만 참고했다.) 다른 방법들도 있는것 같았지만, 이게 제일 명확했다. 더보기 #include #include #include using namespace std; bool topology_sort(vector& di, .. 2022. 5. 5.
[programmers] Lv.3 경주로 건설(c++) 더보기 #include #include #include #include using namespace std; struct Node{ int x, y; int cost; int dir; Node(int x=0, int y=0, int cost=0, int dir=4) : x{x}, y{y}, cost{cost}, dir{dir}{} }; int solution(vector board) { vector x_dir = {-1, 1, 0, 0}; vector y_dir = {0, 0, -1, 1}; vector possible_dir = {{0, 2, 3}, {1, 2, 3}, {0, 1, 2}, {0, 1, 3}, {1, 3}}; int N = board.size(); vector dp(N, vector(N,.. 2022. 5. 3.
728x90

티스토리툴바