공부공간

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 , 변수) 앞의 엔터제거..