본문 바로가기
728x90

DFS4

[Algorithm] 그래프 그래프 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조 정점의 개수 v개, 간선의 개수 e개 일 때 최대 간선의 개수 : v(v-1)/2 선형 자료구조 / 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이 그래프 유형 무향/유향 그래프 : 방향의 유무 가중치 그래프 사이클 없는 방향 그래프 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 그래프 표현 # 노드, 간선의 개수 V, E = 7, 8 # 간선의 연결 (무방향) temp = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7] 위와 같은 입력이 들어왔을 .. 2021. 10. 20.
[BOJ/Python] 14503. 로봇 청소기 📌 문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 📌 문제 접근 방법 바보같이 문제 파악을 잘 못해서 어어어어엄청 헤맸다😣 문제를 찬찬히 살펴보자면, 1) 현재 위치를 청소한다. 2) 현재 위치에서 왼쪽 방향부터 차례로 인접한 칸을 탐색한다. 2-1) 청소할 공간이 있다면, 해당 방향(청소할 공간의 방향)으로 회전하여 전진한다. 2-2) 네 방향 모두 청소할 수 없다면, 바라보는 방향(마지막으로 탐색한 방향)을 유지한 채로 후진한다. .. 2021. 10. 13.
[Algorithm] DFS, BFS 그래프 탐색 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요 두 가지 방법 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS) DFS (깊이우선탐색) 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법 마지막에 만났던 갈림길의 정점으로 되돌아가서 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 DFS 알고리즘 시작 정점 v를 결정하여 반문 정점 v에 인접한 정점 중에서 방문하지 않는 정점 .. 2021. 10. 3.
[SWEA/Python] 4871. 그래프 경로 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 dfs 적용해보기! dfs는 아직도 너무 어렵다😭 코드 구현은 했지만 아직도 알듯말듯,, 이 문제의 경우에는 방향이 있는 경로라서 간선 입력 시 한 번만 입력하면 된다. 📌 코드 - 스택으로 풀기 import sys sys.stdin = open('input.txt') def dfs_stack(v, e): stack = [] stack.append(v) while stack: v = stack.pop() if visited[v] == 0: visited[v] = .. 2021. 8. 24.
728x90

티스토리툴바