simple BFS via golang
simple BFS via golang
Why write this
- 최근 틈틈이 알고리즘 책을 읽고 있습니다.
- 여러가지 알고리즘을 읽고 있지만 본의 아니게 파이썬으로 설명하는 책을 많이 읽게 되었습니다.
- 파이썬으로는 너무나도 간단하게 구현 되는 경우가 많습니다.
- 그러다 보니 이거 golang 으로 작성하면 어떻게 되지? 라는 의문을 가지게 됩니다.
들어가기 전에
- BFS를 python으로 이해하고 나니 golang 에서는 어떻게 구현이 될지 궁금 합니다.
- python 코드는 3.x에서 동작 합니다.
- 해당 알고리즘책은 아래와 같습니다.
- BFS => Breadth-first search
Reference
- Hello Coding 그림으로 개념을 이해하는 알고리즘 - 한빛 미디어
우선 기존의 python 코드를 보겠습니다.
from collections import deque
def search(name):
search_queue=deque()
search_queue+=graph[name]
searched=[]
while search_queue:
person= search_queue.popleft()
print(person+" pop name")
if not person in searched:
if person_is_seller(person):
print(person+" is a mango seller!")
return True
else:
search_queue+=graph[person]
searched.append(person)
return False
def person_is_seller(name):
return name[-1]=='m'
graph={}
graph["you"]=["alice","bob","claire"]
graph["bob"]=["anuj","peggy"]
graph["alice"]=["peggy"]
graph["claire"]=["thom","jonny"]
graph["anuj"]=["slime"]
graph["peggy"]=[]
graph["thom"]=[]
graph["johny"]=[]
search("you")
코드는 you 라는 시작점부터 시작합니다.
- 목표는 m 으로 끝나는 사람을 찾는 겁니다.
- 해당 조건은 취향에 맞춰서 바꿀수 있습니다.
- 책에서는 그림으로 보여 주었지만 방향성이 따로 없다는 것 으로 생각 했을때 tree 형태로 보여줘도 문제 없다고 판단되어서 아래와 같이 그림으로 대체 합니다.
||
- python 에서는 간단하게 hash table (map)을 만듭니다.
설명 전에
- 코드를 만드는 중에 2가지 정도의 딜레이 사항이 있었는데요
- 하나는 golang 에서는 기본적으로 queue 라는 구조가 없더군요. (왜지?)
- 아래와 같이 golang.org doc 에는 queue 를 제외하고 있네요.
- heap Package heap provides heap operations for any type that implements heap.Interface.
- list Package list implements a doubly linked list.
- ring Package ring implements operations on circular lists.
- 아래와 같이 golang.org doc 에는 queue 를 제외하고 있네요.
- 두번째는 hash table 형태를 만드는 거였습니다.
- key, value 형태에서의 array 느낌이 조금 달라서..
golang 으로 만들어 봅시다
- key, value 형태에서의 array 느낌이 조금 달라서..
- 하나는 golang 에서는 기본적으로 queue 라는 구조가 없더군요. (왜지?)
- 우선은 python 에서의 graph 를 만들어 봐야 겠군요.
- golang 에서는 map 이라는 자로구조 가 있으니까 이걸 활용 해 봅니다.
- key 와 value 가 모두 string 의 형태 이고 value 에 대해서는 key 에 대해서는 배열로 값을 가지고 있습니다.
- 사실 이 부분에서 조금 시간이 지체되었습니다.
- 아루래도 다른 언어로 변환 하다 보니 그대로 가져 갈수 없는 부분들이 있어서..
- stacoverflow 에 비슷한 고민을 한 글이 있어서 참고 했습니다.
- https://stackoverflow.com/questions/4286615/how-do-i-create-a-map16bytestring-in-go
- 해당 글은 정확히는 중간에 []가 uri 를 만드는 과정에서 없어져서 구글 검색이 안되거나 주소로 해당 페이지를 찾을수 없을수 있습니다.
- 위의 글을 검색하고 싶다면 다음의 문장을 google 에서 검색하에요.
- How do I create a map[[16]byte][]string in Go
graph := make(map[string][]string)
graph["you"] = []string{"alice", "bob", "claire"}
// https: //stackoverflow.com/questions/4286615/how-do-i-create-a-map16bytestring-in-go
graph["bob"] = []string{"anju", "peggy"}
graph["alice"] = []string{"peggy"}
graph["claire"] = []string{"thom", "jonny"}
graph["anju"] = []string{}
graph["peggy"] = []string{}
graph["thom"] = []string{}
graph["johny"] = []string{}
- 그 다음은 search func 를 만들어 보겠습니다.
- queue 는 결국 어디서 꺼내느냐의 차이 이기 때문에 append 와 slice 로 대체 했습니다.
- contains golang.org 를 찾아 봤지만 찾지 못했기 때문에 간단하게 만들었습니다.
func search(name string, graph map[string][]string) bool {
var search_queue = []string{}
search_queue = append(search_queue, graph[name]...)
var serarched = []string{}
for len(search_queue) > 0 {
person := search_queue[len(search_queue)-1 : len(search_queue)]
search_queue = search_queue[:len(search_queue)-1]
//pop
fmt.Println(person[0] + " is a pop")
if !Contains(serarched, person[0]) { // Contains() 를 만들었다.
fmt.Println("inner contains")
if person_is_sellor(person[0]) {
fmt.Println(person[0] + " is a mango seller!")
return true
} else {
search_queue = append(search_queue, graph[person[0]]...)
serarched = append(serarched, person[0])
}
}
}
return false
}
- 전체 코드를 첨부 합니다.
- 웹에서는
- https://go-tour-kr.appspot.com/#1
- 주소에서도 테스트 가능 합니다.
package main
import (
"fmt"
"strings"
)
func Contains(a []string, x string) bool {
for _, n := range a {
if x == n {
return true
}
}
return false
}
func search(name string, graph map[string][]string) bool {
var search_queue = []string{}
search_queue = append(search_queue, graph[name]...)
var serarched = []string{}
for len(search_queue) > 0 {
person := search_queue[len(search_queue)-1 : len(search_queue)]
search_queue = search_queue[:len(search_queue)-1]
//pop
fmt.Println(person[0] + " is a pop")
if !Contains(serarched, person[0]) {
fmt.Println("inner contains")
if person_is_sellor(person[0]) {
fmt.Println(person[0] + " is a mango seller!")
return true
} else {
search_queue = append(search_queue, graph[person[0]]...)
serarched = append(serarched, person[0])
}
}
}
return false
}
func person_is_sellor(name string) bool {
return strings.EqualFold(name[len(name)-1:len(name)], "m")
}
func main() {
graph := make(map[string][]string)
graph["you"] = []string{"alice", "bob", "claire"}
// https: //stackoverflow.com/questions/4286615/how-do-i-create-a-map16bytestring-in-go
graph["bob"] = []string{"anju", "peggy"}
graph["alice"] = []string{"peggy"}
graph["claire"] = []string{"thom", "jonny"}
graph["anju"] = []string{}
graph["peggy"] = []string{}
graph["thom"] = []string{}
graph["johny"] = []string{}
fmt.Println(search("you", graph))
}
마치며
- golang 의 좋은 점을 알리고 싶어서 쓰고 있는 글인데 왠지 python 의 더 간단한 점을 보여주고 있는거 같네요.
- 그래도 golang 의 static 함은 좋은 거 같습니다. 오류나 애매한 부분을 거의 대부분 제거해 버리는 부분 같은거
댓글남기기