본문 바로가기

DFS5

[백준 1697] 숨바꼭질 with kotlin 문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.출력수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.package com.chanhue.algorithm.백준.실버import jav.. 2025. 5. 4.
[프로그래머스, kotlin] 타겟넘버 재귀를 이용한 문제 풀이 fun solution(numbers: IntArray, target: Int): Int { var answer=0 fun dfs(index: Int, currentSum: Int) { if (index == numbers.size) { if (currentSum == target) { answer = answer + 1 } } else { val add = dfs(index + 1, currentSum + numbers[index]) val subtract = dfs(index + 1, currentSum - numbers[index]) .. 2024. 6. 28.
[프로그래머스 , kotlin] 피로도 연결리스트를 이용한 풀이 ( 스택과 같은 기능으로)fun solution_ff(k: Int, dungeons: Array): Int { val stack = mutableListOf(Triple(k, 0, BooleanArray(dungeons.size))) var maxCount = 0 while (stack.isNotEmpty()) { val (currentK, count, visited) = stack.removeAt(stack.lastIndex) maxCount = maxOf(maxCount, count) for (i in dungeons.indices) { if (!visited[i] && currentK >= dungeo.. 2024. 6. 27.
깊이 우선 탐색(DFS, Depth-First Search) 이란? 깊이 우선 탐색(DFS, Depth-First Search)깊이 우선 탐색 (DFS)는 하나의 순환 알고리즘으로 백트래킹에 사용하는 대표적인 탐색 알고리즘이다. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 주로, 재귀함수 또는 Stack으로 구현할 수 있다.  깊이 우선 탐색의 구현1. 순환 호출 이용def dfs_recursive(graph, start, visited = []):## 데이터를 추가하는 명령어 / 재귀가 이루어짐 visited.append(start) for node in graph[start]: if node not in visited: dfs_recursive(.. 2024. 6. 12.