알고스팟 풀이/조합탐색 썸네일형 리스트형 [알고스팟/ALGOSPOT] 20. JUMPGAME 안녕하세요. 알고라파덕입니다. 20번 문제 JUMPGAME 이 JUMPGAME이란 문제는 동적계획법으로도 해결이 가능하고 DFS(깊이 우선 탐색기법)으로도 해결이 가능하고 BFS(너비 우선 탐색기법)으로도 해결이 가능합니다. 저는 BFS(너비 우선 탐색기법) 을 보여 드리겠습니다. 문제의 요점은 게임판의 숫자만큼 행과 열로 이동을 하여 도착지점(N,N)에 도착 할 수 있는가 없는가를 구하는 문제입니다. ex) 3 2 1 1 1 1 2 2 1 0 이런 입력 데이터에서는 (1, 1)에서 오른쪽으로 2칸 이동하는 경로는 (2, 3)에 도착해 불가능하지만, (1,1)에서 아래쪽으로 2칸 이동하는 경로는 (1, 1) -> (3, 1) -> (3, 3) (3, 3)에 도착해 가능합니다. 그래서 YES를 출력합니다... 더보기 [알고스팟/ALGOSPOT] 7. NQUEEN 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 NQUEEN이라는 문제입니다. 재귀함수를 이용하여 백트래킹을 구현하였습니다. 문제 개요 NxN 크기의 체스판에 N개의 킨을 서로 공격할 수 없도록 올려놓는 퍼즐입니다. 테스트케이스가 주어지고, 테스트 케이스마다 체스판의 크기 N이 입력됩니다. 여기서 N개의 퀸을 배치하는 가지수를 출력해야 합니다. 문제 풀이 N개의 퀸을 배치해야 함으로, 한 줄에는 한 개의 퀸만이 들어가야 됩니다. 이를 이용하여 첫 행에 1~N열에 퀸을 배치하고 배치하였을 때 퀸의 이동경로를 체크합니다. 체크는 chk[][]라는 배열을 만들어 퀸의 이동경로에 포함되면 1을 아니면 0으로 입력합니다. 2번째 행부터 재귀함수를 이용하여 1열~N열 까지의 칸중에서 체크되지.. 더보기 [알고스팟/ALGOSPOT] 6. BOARDCOVER 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 6번 문제는 BOARDCOVER라는 문제입니다! 저는 이 문제를 재귀함수로 DFS(깊이 우선 탐색법)를 구현하여 풀었습니다. 문제 개요 입력에서 테스트 케이스가 주어지면 하나의 테스트 케이스당 (NxM)행렬의 게임판이 주어집니다. 이 게임판에서 '#'은 블록이 있는 부분이고, '.'은 블록이 없는 부분입니다. 그럼 저희는 블록이 없는 부분 '.'을 '#'으로 채워주어야 합니다! 블록의 개수는 ㄱ, ㄴ과 ㄱ, ㄴ의 90도 회전한 블록 4개가 있습니다. 문제 풀이 재귀함수를 이용하여 DFS를 구현하였습니다. 먼저 입력을 받을 때 블록이 없는 부분 '.'부분을 추출해 놓으면 속도를 더 빠르게 할 수 있습니다. 탐색도 쉽게 할 수 있구요! 예를 들어 입.. 더보기 [알고스팟/ALGOSPOT] 4. CLOCKSYNC 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 CLOCKSYNC라는 문제인데요~ 12시 3시 6시 9시로 되어있는 시계를 스위치를 이용해서 모두 12시로 바꾸는 최소로 눌러야할 스위치의 개수를 구하라 라는 것이에요. 모두 12시로 바꿀 수 없다면 -1을 출력해야 하구 시간초는 10S가 되겠어요~ 먼저 이 문제의 올바른 풀이법은 BFS(너비우선탐색)라고 생각해요~ 흠 먼저 기존 상태에서 사용 할 수 있는 스위치를 판별을 하여 가지를 뻗어나가요. 가지를 뻗다 모두 12시가 되면 그 방법이 항상 최소 스위치 개수가 되기 때문에 그 수를 출력해요. 대략적인 그림을 그렸는데 저기 트리의 맨윗부분 기존에서 예를 들어 스위치를 5개 사용하였다면 다른 형태의 5개의 정보가 QUEUE 배열에 들.. 더보기 이전 1 다음
