# DFS

khyup0629

백준 24479번 깊이 우선 탐색 1

hereokay

자료구조의 한 종류, 정점(vertex)와 간선(edge)로 이루어진 자료구조.즉. 점과 선으로 이루어진 자료구조. 트리는 부모노드와 자식노드가 간선으로 연결되어 있으므로, 그래프의 한 예시이다.대표적으로 DFS와 BFS가 있다.정점에서 한 간선을 통해 다른정점으로 이

lee-goeun

문제링크https://programmers.co.kr/learn/courses/30/lessons/87946XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하

murjune

https://www.acmicpc.net/problem/2629 저울에 추를 왼쪽으로 올리는 경우, 안 올리는 경우, 오른쪽으로 올리는 경우로 나누고, dfs를 돌린다. 중복되는 경우를 방지하기 위해 2차원 테이블 didx를 사용했다. didx : idx

seongmini

📝 문제 https://www.acmicpc.net/problem/2583 💬 풀이 방법 알고리

murjune

https://www.acmicpc.net/problem/2098 외판원 순회는 n의 범위가 10개인지 16개인지에 따라 풀 수 있는 알고리즘이 다르다. 10개인 경우(외판원 순회2)는 완전탐색, 백트래킹 기법으로 비교적 쉽게 풀 수 있으나, 고작 도시가 6개 추가

dev-junku

문제 풀러 가기!문제를 읽다보면, 가장 위쪽 방향부터 찾으면 되겠다고 생각드는 문제였다.(이부분이 Greedy다)사실 내 풀이는 최악의 시간복잡도가 1초 1억이 넘는다. Python이기 때문에..... 핸디캡이 붙은 듯 하다.여튼 가장 위쪽 부터 탐색을 시도하면 그 다

jeajea0127

BFS 너비 우선 탐색 , 시간 복잡도 O(노드수 + 엣지수) 구현 코드 need_visit 큐(방문할)와 visited 큐(방문한)를 생성한다. DFS 깊이 우선 탐색 , 시간 복잡도 O(노드수 + 엣지수) 구현 코드 need_visit 스택(방문할)과 visited큐(방문한)를 생성한다.

taehyeon96

링크 : https://www.acmicpc.net/problem/1697

imchanyang

문제 풀이 > 코드

yoohoo030

섬에서 다른 섬까지 다리를 하나 건설할 때, 다리의 길이의 최솟값을 구해야 한다. 📍 몇시간동안 이 문제만 붙잡고 있었다. 분명 로직은 완벽한데 자꾸 이상한 값이 나와서... 몇시간동안 디버깅한 결과 찾은 오류의 원인은 .. 큐를 비워주지 않아서 생겼던

taehyeon96

링크 : https://www.acmicpc.net/problem/2178이건 BFS네 -> 동빈나에서 같은 문제 있었음다른점 : 테스트케이스가 다양함 => n x n 행렬이 아닌, n x m 행렬임을 주의한다!!!

dgh03207

https://www.acmicpc.net/problem/10819N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.|A0 - A1| + |A1 - A2| + ...

taehyeon96

링크 : https://covenant.tistory.com/132링크 : https://velog.io/@taehyeon96/3.-%EC%9D%B4%EC%BD%94%ED%85%8C-DFS-BFS-%EA%B0%9C%EC%9A%94-%EB%A9%94%E

dgh03207

https://www.acmicpc.net/problem/2529두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어,

yoohoo030

한 개의 순환선과 여러 개의 지선으로 이루어진 그래프가 주어진다. 해당 위치의 인덱스가 순환선인 경우에는 0, 지선일 경우에는 순환선까지의 거리를 출력해야 한다. BFS와 DFS를 이용하여 해결할 수 있다.

nnakki

BFS 시작점을 큐에 넣는다. 시작점을 방문체크한다. 큐가 비었다면 끝내기 큐가 비지 않았다면 큐에 최상단에 있는 노드를 꺼낸다. 해당 노드와 인접한 노드를 탐색하여, 방문하지 않은 노드라면 방문체크를 하고, 큐에 넣어준다. 3,4를 반복

jeaseong

유튜브 '동빈나'님의 채널에서 얻은 정보로 알고리즘의 시작은 '그리디'라는 생각으로 시간이 날 때마다 그리디를 풀어왔다.

yoohoo030

게임판에 사각형 사이클이 존재하면 Yes를, 존재하지 않으면 No를 반환해야 한다. 📍 DFS를 이용하여 풀 수 있다. 📍 현위치에서 상하좌우로 계속해서 나아가되 다시 본래의 위치로 돌아오면 flag에 true값을 할당해준다.

taehyeon96

BFS는 재귀 X이다.따라서 BFS 안에 큐 생성한다시작 포인트 일단 넣는다while queue현위치 = popleft()for 다음위치(또는 다음 노드) 가져와링크 : https://www.youtube.com/watch?v=7C9RgOcvkvo내가 잘못 푼