너비우선탐색문제

www.codingame.com/ide/puzzle/skynet-revolution-episode-1

Coding Games and Programming Challenges to Code Better

주어진 그래프에서 Agent가 출구로 나가지 못하도록 노드 사이의 간선을 끊는 것이 이 게임의 목적이다.

즉, Agent에서 출구까지의 경로를 찾고 마지막 간선을 찾아 출력(끊기)하는 것이 목표라 할 수 있다.

 

1. 그래프만들기

노드는 자신의 이름(숫자)과 자식노드들로 구성되어있고, 그래프는 노드들의 집합이라 할 수 있다.

따라서 노드 클래스를 하나 작성하자

class Node:
	__init__(self, number):
    	self.number = number
        self.parent = []
        self.children = []
        
	connect(self, x):
    	self.children.append(x)

parent는 나중에 짧은 경로 전체를 출력할 때 어디서 내려온 것인지 확인하기위해 추가했다. 

 

다음으로 그래프 클래스를 작성해보자

class Graph:
	__init__(self):
		self.nodes = {}
	connect(self, x,y):
		if x not in self.nodes:
			self.nodes[x] = Node(x)
		if y not in self.nodes:
			self.nodes[y] = Node(y)
		self.nodes[x].connect(self.nodes[x])
		self.nodes[y].connect(self.nodes[y])

이를 이용해서 두 개의 노드가 입력될 때마다 graph.connect(n1,n2)를 입력하여 그래프를 완성한다.

 

 

2. 가장 짧은 경로 찾기

좌측과 같은 그래프가 있다면 너비우선찾기는  0->1->2->3->4->5 순서로 진행하게 된다. 이 때 출발이 0이고 도착이 5인 경로를 찾으려면 어떻게할까?

일단 너비우선탐색으로 5를 찾은 후 찾았다면 5->5의 부모 2->2의부모 0 이렇게 출발점 0까지 노드의 부모를 타고 올라갈 것이다.

 

먼저 너비우선탐색으로 5를 찾는 것을 코드로 나타낸다 생각해보자.

 1)가장 상단의 노드는 {0}이고 0은 5가 아니기 때문에 제외되고 0의 자식들이 다음 찾을 타겟이 된다.

 2)다음 찾을 타겟집단은 0의 자식인 {1,2} 이다. 먼저 1을 보면 1은 5가 아니기 때문에 제외된다. 

제외되면서 1의 자식인 3이 2 다음으로 찾을 타겟집단에 추가되어 {2,3}이 된다.

 3)찾을 타겟집단{2,3}에서 첫번째 요소인 2 또한 5가 아니므로 제외되고, 2의 자식인 4와 5가 추가된다

 4){3,4,5}에서 찾다가 결국 5를 만나게 된다.

즉 찾을 대상 노드들을 순서대로 넣어놓은 리스트(target_list)와 제외된 노드들을 넣어놓은 리스트(ex_list)를 만들어서 탐색을 진행하면 된다.

 

다음으로 찾은 후 부모를 타고 올라가 경로를 만들어야한다.

이는 타겟집단에 넣을 때 parent 정보를 함께 넣고 5를 찾았을 때 parent 속성을 타고 올라가면 된다.

find_shortest_path(self, start, end):
	target_list = [[self.node[start]]]
	ex_list = []
    
    while target_list:
    	element = target_list.pop(0)
        
        #출구를 찾은 경우
        if element.number == end:
			path = []
			while element.number != start:
				path.append(element.number)
				element = element.parent
			path.append(start)
			return path[::-1]
        
        #출구를 못찾은 경우
        else:
        	for child in element.children:
            	#타겟리스트나 확인해서 제외된 리스트에 존재하지 않는 경우만 넣는다.
            	if child not in ex_list and child not in target_list:
                    target_list.append(child)
            		ex_list.append(element)
				else:
                	continue