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

링크 https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 접근 물과의 상호작용을 확인 하면서 비버굴로 들어가기 위한 최소 거리 도출 이동조건 고슴도치 영역이내 돌이 아님 물이 차오르지 않을 예..

링크 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. www.acmicpc.net 접근 입력과 함계 영역을 색칠한다 for y =m) continue; if(visited[ny][nx] || map[ny][nx] == 1) c..

링크 https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 접근 - 순열 생성을 통해 SCV의 공격 순서를 정한다 - n이 3가지 제한되어 있으므로 3! = 6 이다 - typedef vector scv 로 scv의 상태를 정한다 - 공격횟수를 저장하기 위헤 map 를 사용한다 - 만약 hp가 0이상인 scv가 하나도 없다면 탐색을 멈추고 도달 하기 까지의 거리를 반환한다 #include #include #include #include #include usi..

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

문제 바로가기 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..