sladuf
200
sladuf
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (83)
    • ๐Ÿ“š Programming (32)
      • Swift (13)
      • JAVA (2)
      • Python (6)
      • SQL (6)
      • Web (5)
    • ๐Ÿ“ฑ iOS (25)
      • Base (7)
      • SwiftUI (9)
      • UIKit (7)
      • ์ธ๊ฐ• & ์ฑ… (2)
    • ๐Ÿ”— Algorithm (20)
      • Python (12)
      • Swift (3)
      • Tip (5)
    • ๐Ÿ—‚ ETC (6)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

ํƒœ๊ทธ

  • ์Šค์œ„ํ”„ํŠธ
  • Swift

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๊ธ€์“ฐ๊ธฐ ์„ค์ •
hELLO ยท Designed By ์ •์ƒ์šฐ.
sladuf

200

[Algorithm] ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ BFS / ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ DFS
๐Ÿ”— Algorithm/Tip

[Algorithm] ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ BFS / ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ DFS

2020. 8. 24. 15:50

 

 

๊ฐœ์ธ์ ์œผ๋กœ ์–ด๋ ค์›Œ ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜,,

 

์•Œ๊ณ ๋ฆฌ์ฆ˜

BFS๋Š” FIFO๋ฅผ ์›์น™์œผ๋กœ ํ•˜๋Š” Queue๋กœ ๊ตฌํ˜„ํ•œ๋‹ค.

ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•˜๋Š” ์ฒซ ๋…ธ๋“œ(root)๋ฅผ queue์— ๋„ฃ๊ณ  ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•œ๋‹ค.

A. queue์—์„œ ๋…ธ๋“œ๋ฅผ ๊บผ๋‚ธ๋‹ค.

B. ๊บผ๋‚ธ ๋…ธ๋“œ์™€ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ ์ค‘ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๊ณ  queue์— ๋„ฃ๋Š”๋‹ค.

queue์— ๋…ธ๋“œ๊ฐ€ ์—†์–ด์งˆ ๋•Œ ๊นŒ์ง€ AB๋ฐ˜๋ณต

 

๊ตฌํ˜„

 

 

def bfs(graph, root):
	visit = list()
	queue = [root]

    #AB๋ฐ˜๋ณต
	while queue:
		temp = queue.pop(0)
		if temp not in visit:
			print(temp)
			visit.append(temp)
			queue.extend(graph[temp])

 

 

์•Œ๊ณ ๋ฆฌ์ฆ˜

DFS๋Š” LIFO๋ฅผ ์›์น™์œผ๋กœ ํ•˜๋Š” Stack์œผ๋กœ ๊ตฌํ˜„ํ•œ๋‹ค.

ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•˜๋Š” ์ฒซ ๋…ธ๋“œ(root)๋ฅผ stack์— ๋„ฃ๊ณ  ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•œ๋‹ค.

A. stack์˜ ์ตœ๊ทผ ๋…ธ๋“œ๋ฅผ ํ™•์ธํ•œ๋‹ค.

B. ํ™•์ธํ•œ ๋…ธ๋“œ์™€ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ ์ค‘ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๊ณ  stack์— ๋„ฃ๋Š”๋‹ค.

C. ์ธ์ ‘ํ•œ ๋…ธ๋“œ ์ค‘ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ๊ฐ€ ์—†๋‹ค๋ฉด stack์—์„œ ๋…ธ๋“œ๋ฅผ ํ•˜๋‚˜ ๊บผ๋‚ธ๋‹ค.

stack์ด ๋…ธ๋“œ๊ฐ€ ์—†์–ด์งˆ ๋•Œ ๊นŒ์ง€ ABC ๋ฐ˜๋ณต

 

๊ตฌํ˜„

 

 

def dfs(graph, root):
	visit = list()
	stack = [root]
 
	#ABC๋ฐ˜๋ณต
	while stack :
		temp = stack.pop()
		if temp not in visit :
			print(temp)
			visit.append(temp)
			stack.extend(graph[temp])

 

๋”๋ณด๊ธฐ

graph info

 

code

graph = {'A': set(['B', 'C', 'E']),
         'B': set(['A', 'D', 'F']),
         'C': set(['A', 'G']),
         'D': set(['B']),
         'E': set(['A', 'F']),
         'F': set(['B', 'E']),
         'G': set(['C'])}
์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'๐Ÿ”— Algorithm > Tip' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[Python] ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ (DP)  (0) 2022.02.17
[Python] ์ตœ์†Œํž™(MIN heap) / ์ตœ๋Œ€ํž™(MAX heap)  (0) 2022.01.31
[Algorithm] LCA ์•Œ๊ณ ๋ฆฌ์ฆ˜  (0) 2021.03.28
[Algorithm] Dijkstra ๋‹ค์ต์ŠคํŠธ๋ผ ์ตœ๋‹จ ๊ฒฝ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜  (0) 2021.03.11
    '๐Ÿ”— Algorithm/Tip' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [Python] ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ (DP)
    • [Python] ์ตœ์†Œํž™(MIN heap) / ์ตœ๋Œ€ํž™(MAX heap)
    • [Algorithm] LCA ์•Œ๊ณ ๋ฆฌ์ฆ˜
    • [Algorithm] Dijkstra ๋‹ค์ต์ŠคํŠธ๋ผ ์ตœ๋‹จ ๊ฒฝ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜
    sladuf
    sladuf

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”