너비우선탐색3 [백준] 16928번 뱀과 사다리 게임 JAVA (자바) 풀이 문제 16928(BFS) : 주사위를 조작해 원하는 수를 만들면 최소 몇 번만에 도착할까 게임은 크기가 10×10이고, 총 100개의 칸으로 된 보드판은 1~100까지 수가 적혀있다 주사위를 굴려 나온 수만큼 이동 : 예) 현위치 = i / 주사위 = 4라면 i+4번 칸으로 이동 : 도착칸 = 사다리 경우 위로 이동 / 도착칸 = 뱀 경우 뱀을 따라 이동 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있다 (동시에 둘 다 갖는 경우는 없다) : 게임의 목표 = 1번 칸에서 시작해서 100번 칸에 도착하는 것 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값 구하기 [입력] : 첫째 줄에 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(.. 2024. 7. 3. [백준] 13549번 숨바꼭질 3 JAVA (자바) 풀이 문제 13549(BFS) : 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다 현 위치가 X일 때 걷기 = 1초 후에 X-1 또는 X+1로 이동 순간이동 = 0초 후에 2*X의 위치로 이동 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구해라 [입력] : 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K [출력] : 동생을 찾는 가장 빠른 시간을 출력 [문제접근] 1. 기존 숨바꼭질 1697번과 차이점!기존 문제에서는 모든 이동이 동일한 1초를 소요현 문제에서는 순간 이동은 0초 / 걷기 이동만 1초 소요 2. 출력 배열 사용하지 말고 큐에다 넣어버리기count[] 배열보다 .. 2024. 7. 3. 탐색 알고리즘 (브루트포스, DFS, BFS, 백트래킹) 탐색데이터 구조 내에서 가능한 경우의 수를 탐색해 최적의 결과를 찾는 방법선형 탐색 알고리즘 순차적 탐색이진 탐색비선형 탐색 알고리즘트리나 그래프 같이 복잡한 형태에 사용dfs / bfs 1. 브루트 포스완전 탐색모든 경우의 수 탐색단순하지만 경우의 수가 많아서 비효율적일 수 있다 2. DFS 깊이 우선 탐색그래프 또는 트리에서 모든 경로 탐색한 방향으로 깊숙이 노드 탐색 후 더이상 갈 곳이 없으면 다른 방향 탐색스택 / 재귀 함수 사용 3. 백트래킹DFS의 확장 개념해결 가능성 없는 경로일 경우 탐색 중지하고 되돌아가 다른 경로 탐색 4. BFS 너비 우선 탐색시작 노드에서 가까운 노드부터 탐색같은 깊이 층의 노드들 모두 탐색 후 층 내려가면서 탐색큐 함수 사용최단 경로 문제 알고리즘 선택 가이드 ▣.. 2024. 4. 30. 이전 1 다음
