넘어지고 일어나기 넘어지고 일어나기

링크 : https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 접근 - dfs를 통해 인접한 같은 컬러의 뿌요를 탐색해 나간다 - 탐색으로 인해 추가된 뿌요의 갯수가 4개 이상이라면 터뜨린다 - 터뜨린 빈 공간에 나머지 뿌요를 하단으로 밀착시킨다 - 시뮬레이션 + dfs 문제 *주의 - 연쇄의 수를 세는 것이므로 가능한 모든 뿌요를 터뜨린 다임 카운트를 1 증가 시킨다 #include #include using namespace std; struct pos{int y, x;}; vector brokens; typedef vector t..

링크 : https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다. 막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, www.acmicpc.net 접근 - 문제를 그대로 구현한다 - 막대길이를 저장하기 위해 vector를 사용한다 - 막대기를 내림차순으로 정렬한다 - 맨 끝의..

링크 : https://www.acmicpc.net/problem/1963

Link : https://www.acmicpc.net/problem/2668 접근 dfs cycle을 이루는 노드들이 몇개인지 확인 한다 1 2 3 4 5 6 7 3 1 1 5 5 4 6 1 - 3 - 1 3 - 1 - 3 5 - 5 pivot 과 숫자를 함께 넘겨 준다 만약 pivot으로 부터 출발하여 노드 값이 pivot과 동일한 숫자가 나온다면 답에 추가 한다 dfs(int pivot, int node){ if(visited[node]) if( pivot == node ) ret.push_back(pivot) else visited[node] = true dfs(pivot, node) } #include #include #include #include #include #define MAX 101 ..

문제 바로가기 Type : BFS 접근 (1) 경로의 수를 담기 위한 배열을 사용 한다. (2) 한 노드 까지 도달 할 수 있는 경로의 수는 직전 노드까지 도달 할 수 있는 경로수들의 합 이다. (3) 만약 방문 하지 않은 노드 라면 미방문 노드의 경로수를 현재 노드 까지의 경로수로 갱신한다. (4) 만약 방문한 노드 라면 현재 노드 까지의 경로수를 더해 준다. 플로우 차트 구현 코드 #include #include #include #define MAX 100001 using namespace std; int arr[MAX]; int paths[MAX]; map dist; int n, k; bool inRange(int x){ return 0 0; } void bfs(int start){ queue q;..

문제 바로가기 Type : BFS 접근 (1) 외부에서 접근 가능 하도록 지도 주의를 빈곳으로 둘러싼다. (2) 한번의 BFS 당 열쇠를 한개 이상 찾거나 혹은 문서를 발견하는 일을 시도 한다. (3) 만약 시도에 성공 했다면 다시 한번 BFS를 시도 한다. (4) 만약 시도에 실패 했다면 BFS 를 종료 하고 다수의 시도에서 찾은 문서의 갯수를 출력 한다. (5) BFS 탐색 (1) 범위를 벗어나거나, 이미 방문 했거나, 벽이라면 탐색을 하지 않는다. (2) 만약 탐색 지점에 문서가 있다면 카운트 하고, 성공한 시도로 정의한다. (3) 만약 대문자 알파벳을 만났으나, 열쇠가 없다면 탐색을 하지 않는다. (4) 만약 소문자 알파벳을 만났다면, 열쇠를 추가 하고 성공한 시도로 정의한다. 플로우 차트 (1)..

문제 바로가기 Type : BFS 접근 (1) 가능한 모든 물통의 경우를 탐색 하기 위해 BFS 탐색을 실시 한다. (2) 하나의 상태에 진입 할때마다 가능한 모든 경우로 물을 옮겨 본다. (3) 한번 물을 옮길 때 마다 두가지 경우가 가능 하다. * 다른 물통의 물을 전부 채울 수 있는 경우 * 붓는 물통의 물이 전부 비게 되는 경우(4) 다른 물통의 물을 전부 채울 수 있는지 여부는 (size[dst] - water[dst]) < water[src] 로 검사 한다. 플로우 차트 구현 코드 #include #include #include #include #include using namespace std; typedef vector buckets; buckets size; vectorwaters; vo..

문제 바로가기 Type : BFS 접근 문자열 BFS 트리 탐색을 통해 주어진 상태로 부터 목표 상태까지 도달 할 수 있는 최소 거리를 구한다. Tree Example 123495786 193425786 913425789 139425789 (1) 위치 및 현재 상태 파악 string cs = q.front(); int cp = cs.find(&#39;0&#39;); int sy = cp / 3; int sx = cp % 3; 2차원 배열을 사용하지 않고 몫과 나머지를 통해 y와 x 값을 도출 할 수 있다 (2) 만족한 범위 내에서 요소의 순서를 바꾼 새로운 문자열(상태)을 생성 한다. int ny = sy + dy[i]; int nx = sx + dx[i]; np = ny*3 + nx; swap(ns[c..