공부공간

입력받은 배열의 모든 값을 확인해주면서 W가 아닌 부분에서의 갈수있는 모든 경로를 BFS를 통하여 구해준다. 가장 큰 길이를 가진 두점이 정답이 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #include #include using namespace std; char map[51][51]; bool visit[51][51]; int a, b; void input() { cin >> ..

DP를 이용해서 풀까 고민하다가. N의 최댓값을 보고 재귀함수로 풀어보았다. 대각선으로 움직일때에 MAP에 추가적으로 NY-1 , NX-1을 확인해주고 90도 로 움직이는 경우의수를 제외하고 파이프의 끝방향의 좌표를 재귀함수의 인자값으로 넘겨주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include #define MAX 17 using namespace std; int N,res; int map[MAX][MAX]; pair dir[3] ={ {0,1}, {1,0}, {1,1} }; void input..

map에서 1인곳만 방문하면서 N-1 , M-1까지 최소로 갈수있는 경우의 수를 구하는 문제이다. 건너갈 칸수만 구하면되므로 BFS를 이용하여 처리하였다. 자꾸 메모리 초과가 나서 이유를 생각해 보았는데, VISIT 배열을 처리하는 부분때문이 였다. 처음 Queue에서 뽑아서 Y,X의 VISIT을 True로 해주는 식으로 탐색하였는데 메모리초과가 났다. 같은 길이의 경로를 가진 곳을 탐험할때 Queue에 똑같은 좌표가 두번들어가는 경우가 발생하여 메모리가 초과되었던 것이다. 문제에서 확인하는 메모리 조건은 입력의 최댓값으로 배열을 선언하거나, 크기가 큰 값을 받는 것이아닌 큐의 순회횟수가 중요하다는 것을 알았다. 그리고 추가적으로 cin.ingore() -> getline(cin , 변수) 앞의 엔터제거..

피보나치 함수에서 0과 1이 몇번 출력되었는지 출력하는 문제이다. 피보나치 수열을 살펴보면 n>=2 에 대하여 fibo(n) = fibo(n-1)+fibo(n-2) 의 점화식을 구할수 있다. 여기서 0과 1이 나온 횟수를 적어보았다. n= 0일때 -> 1 , 0 n= 1일때 -> 0 , 1 n= 2일때 -> 1 , 1 n= 3일때 -> 1 , 2 n= 4일때 -> 2 , 3 피보나치 수열과 마찬가지로 0과 1의 횟수또한 피보나치 수열점화식을 따른다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

BFS 를 사용하는 기본 형태의 변형이다. 지훈이가 이동하기 전, 불 또한 4 방향으로 퍼져나가기 때문에, 불에 의하여 변한 지형을 먼저 처리하고, 이후 지훈이가 이동가능한 칸으로 움직인다. 이때, 가장자리에 지훈이가 이동하였다면 탈출한다.

BFS 알고리즘을 사용하는 문제의 변형이다. 문제 해결 접근 방법은 다음과 같다. 문자열 행렬 탐색 - 색깔 요소 검출시 상하좌우 탐색 - 탐색된 좌표는 큐에 저장 - 큐에 저장된 좌표쌍의 수가 4 이상이라면, 블록이 파괴된다. - 해당 연산을 더 이상 블록이 터지지 않을 때 까지 실행한다.