본문 바로가기
반응형

BFS3

[프로그래머스] 게임 맵 최단거리(level2) (자바) package com.programmers; import java.util.LinkedList; import java.util.Queue; /** * https://programmers.co.kr/learn/courses/30/lessons/1844?language=java * 방문 처리를 해버리면 다른 루트에서 접근할 때 도착하지를 못한다. bfs일 경우 최단 거리로 갈 수 있기 때문에 방문처리를 false로 바꿀 일이 필요 없다. */ public class 게임맵_최단거리 { public static void main(String[] args) { int[][] maps = { {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 1}, .. 2021. 11. 14.
[백준] [우선탐색] DFS와 BFS 1260 (파이썬) 개념 2021.03.07 - [Algorithm & Data structure] - [알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색) [알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색) DFS (깊이 우선탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료구조( or 재귀함수)를 이용한다 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 seongbindb.tistory.com 스케치 코드 import sys from collections import deque def bfs(graph,start, visited_bfs): q = deque([start]) # 1 visited_bfs[start] = True while q: v = q.po.. 2021. 3. 14.
[알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색) DFS (깊이 우선탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료구조( or 재귀함수)를 이용한다 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 더이상 2번의 과정을 수행할수 없을 때까지 반복합니다. BFS (너비 우선 탐색) 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 큐 자료구조를 이용한다. 탐색 시작노드를 큐에 삽입하고 방문처리를 합니다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 합니다. 더 이상 2번의 과정을 수행할 수 .. 2021. 3. 7.
반응형

티스토리툴바