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 형태로 보여줘도 문제 없다고 판단되어서 아래와 같이 그림으로 대체 합니다.

| treeForBFS |

python 에서는 간단하게 hash table (map)을 만듭니다.

설명 전에

코드를 만드는 중에 2가지 정도의 딜레이 사항이 있었는데요
1. 하나는 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.
2. 두번째는 hash table 형태를 만드는 거였습니다.
  - key, value 형태에서의 array 느낌이 조금 달라서..
    golang 으로 만들어 봅시다
우선은 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 함은 좋은 거 같습니다. 오류나 애매한 부분을 거의 대부분 제거해 버리는 부분 같은거

Twitter Facebook Google+ LinkedIn

Peter Yoon

simple BFS via golang

simple BFS via golang

Why write this

들어가기 전에

Reference

우선 기존의 python 코드를 보겠습니다.

코드는 you 라는 시작점부터 시작합니다.

설명 전에

golang 으로 만들어 봅시다

마치며

공유하기

댓글남기기