공부공간

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ... www.acmicpc.net 나이트가 이동할수 있는 경로를 FOR문으로 설정하여서 돌려준다. VISIT 배열로 갔던곳을 다시 가지않게 설정해준다. 1 2 3 4..

입력받은 배열의 모든 값을 확인해주면서 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 >> ..

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

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

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

재귀함수를 통하여 해결할 수 있는 문제이다. 수를 입력받는 행렬을 선언하여 뽑을 수 있는 수를 입력 받고, 재귀 함수를 통하여 독일 로또의 출력 숫자인 6개로 출력 행렬이 채워지면 출력한다.

기본적인 형태의 DFS 알고리즘 문제의 변형이다. 문제 풀이의 접근방식은 다음과 같다. 현재 배열(일반인 시각), 변형 배열(적록 색약자의 시각) 을 선언하여 DFS 알고리즘을 통하여 구역의 개수를 세어주면 쉽게 해결할 수 있다.

좌측상단에서 시작하여서 가본적이 없는 알파벳을 찾아서 상하좌우로 진행하였을때에, 최장거리를 출력하는 문제이다. 문제는 'Z'-'A' 크기(25)만큼의 visit배열을 생성하고 DFS를 돌리면서 가본적이 없는 알파벳으로 진행하면서 PATH값을 최대로 갱신한다. 탐색할 노드에 대한 방문처리만 잘해주면 쉽게 풀리는 문제였다.