그래프 군집 구하기

문제

 

문제를 간략히 설명하자면,

n 개의 city가 있고 여기에 도서관(lib)을 세워야하고 인접한 city에는 도서관이 하나만 있으면 되는데 이때 최소비용을 구하는 문제입니다. (너무 내용을 축약했기 때문에 상세 조건들은 문제를 보셔야합니다)

 

최초 아이디어

def roadsAndLibraries(n, c_lib, c_road, cities):
   
    while q:
        x, y = q.popleft()

        if x not in visited and y not in visited:
        #
        elif x not in visited or y in visited:
        #
    
    return min(n * c_lib, result)

 

리스트가 [[1,2], [3,4] ...] 이런 모양이기 때문에 x, y 요소를 얻어내어서 각 점이 방문했는지를 검사하면 되겠습니다. 그런데 이 아이디어는 심각한 오류가 있습니다. [[1,2], [3,4], [2,3]] 과 같은 리스트는 [2,3] 일때 앞에서 2와 3은 이미 방문했기때문에 간선이 연결되지 않는 오류가 있습니다. 그래프 문제는 어느정도 절자척인 단계가 있어서 스텝별로 나누어 설명하고자 합니다.

 

 

 

Step1. 주어진 데이터로 Graph 사전을 만들라

from collections import deque

def roadsAndLibraries(n, c_lib, c_road, cities):
    graph = {}
    visited = []
    cost = 0
    
    def bfs():
    
    for i range(1, n+1):
    	bfs(i)
    
    return cost

 

기초 공사는 아래와같은 스텝으로 하시면 됩니다.
1. 양방향 queue를 불러오기

2. graph라는 이름의 Dictionary 선언하기

3. 방문 여부를 체크하는 visited 리스트 생성하기

4. bfs 선언

5. bfs 호출

6. 최소값 반환

 

Step2. 그래프 초기화

def roadsAndLibraries(n, c_lib, c_road, cities):
    # init graph
    graph = {i : [] for i in range(1, n+1)}
	# => graph = {1:[], 2:[], 3:[], ...}
    
    # 중요포인트! x,y를 앞뒤로 번갈아가면서 넣어줘야 완벽하게 양방향 간선들이 그려진다.
    for x,y in cities:
    	graph[x].append(y)
        graph[y].append(x)

 

그래프 딕셔너리를 초기화 하는 방법이다. 또는 아래와 같이 작성해도 된다

from collections import defaultdict, deque

def roadsAndLibraries(n, c_lib, c_road, cities):
	graph = defaultdict(list)

 

그리고 그래프의 모든 점에서부터 BFS를 실행해야 하므로, 방문 여부를 체크하면서 반복하도록 한다.

그런데 bfs는 무슨 값을 리턴해야될까?

 

 

Step3. BFS 실행부분 구현

def roadsAndLibraries(n, c_lib, c_road, cities):

    def bfs():
    	return edge
        
    for i range(1, n+1):
    	if i not in visited:
	    	edge += bfs(i)

 

각 vertex에서 BFS를 돌면서 우리가 구해야하는 것은 road (edge)수 이므로 edge의 합을 구하도록 하자.

 

Step4. BFS 구현

def roadsAndLibraries(n, c_lib, c_road, cities):

    def bfs(start):
    	edge = 0
        visited.append(start) #최초 방문을 찍고 들어가야한다. 아래서는 최초 점의 인접 점들을 찍음.
    	q = deque([start])
        # 여기서 주목할 점은 인자로 i를 받았지만 딕셔너리가 리스트형을 가지므로 []을 씌워줘야함

        while q:
            cur = q.popleft()
            #그래프 이동 로직! 최초 방문점의 인접 점들을 찾는다.
            for neighbor in graph[cur]:
                if neighbor not in visited:
                    visited.append(neighbor)
                    #방문하지 않은 인접 점들은 큐에다가 담아 다음번에 방문하도록한다.
                    q.append(neighbor)
                    edge += 1
    	return edge
        
    for i range(1, n+1):
    	if i not in visited:
	    	edge += bfs(i)
            
    return cost

 

1. 최초 점을 방문처리

2. 최초 점을 큐에 넣는다

3. 큐를 소진시키는데, 우선 최초 점을 소진 시킨다(cur = q.popleft())

4. 최초 점을 기준으로 인접 점들을 가지고 하나씩 방문한다

5. 인접 점들의 방문을 체크하고, 방문하지 않았으면 Q에 담아 다음 회차에 방문할 수 있도록 하자.

 

위와같이 하고보니 cost를 구하는 로직이 빠졌다.

 

Step5. 결과 연산하기

def roadsAndLibraries(n, c_lib, c_road, cities):

	cost = 0
            
    for i range(1, n+1):
    	if i not in visited:
	    	edge += bfs(i)
			#이미 bfs 한사이클 돌면서 하나의 그래프가 생겼으니 c_lib은 1개만 존재한다. 
            cost += c_lib*1 + c_road*edge
            
    return cost

 

그런데 위 코드는 시간초과 문제가 발생했습니다.

 

 

개선 포인트

visited = set()
	
    visited.add(start)
    	visited.add(neighbor)

 

vertex가 많아지면 list 에서 선형검사 하는데 시간이 많이듭니다.

if i not in visited:

위 구문에서 선형 검사를 하는데 너무 많은 메모리를 잡아먹는 것을 발견했습니다.

이는 set과 list의 성능 차이를 살펴보면 알 수 있는데, set은 해시 테이블을 사용하여 원소의 존재 여부를 빠르게 확인할 수 있어서 시간복잡도가 O(1)에 가깝습니다. 반면에 list는 선형 검색을 수행해야 하므로 시간복잡도가 O(n)입니다.

 

 

예외처리

def roadsAndLibraries(n, c_lib, c_road, cities):
    if c_lib <= c_road:
        return n * c_lib

모든 city에 도서관을 짓는게 비용이 싼 경우가 있다고 하였으니 위와같이 예외를 추가해주자

 

 

전체 코드

from collections import defaultdict, deque

def roadsAndLibraries(n, c_lib, c_road, cities):
    if c_lib <= c_road:
        return n * c_lib
    
    graph = {i : [] for i in range(1, n+1)}
    for x,y in cities:
        graph[x].append(y)
        graph[y].append(x)
    visited = set()
    cost = 0
    
    def bfs(start):
        edge = 0
        visited.add(start)
        q = deque([start])

        while q:
            cur = q.popleft()
            for neighbor in graph[cur]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    q.append(neighbor)
                    edge += 1
        return edge
    
    for i in range(1, n+1):
        if i not in visited:
            edge = bfs(i)
            cost += c_lib*1 + c_road*edge
    return cost

 

 

 

DFS로 구현하기

 def roadsAndLibraries(n, c_lib, c_road, cities):
     if c_lib <= c_road:
        return n * c_lib
    
    graph = {i : [] for i in range(1, n+1)}
    for x,y in cities:
        graph[x].append(y)
        graph[y].append(x)
    visited = set()
    cost = 0
    
    def dfs(start):
        visited.add(start)
        # DFS는 재귀이므로 [1:2] 간선을 연결할떄 [start:neighbor]면 beighbor가 for문을 돌때 적어도 1을 반환해야한다.
        count = 1
        for neighbor in graph[start]:
            if neighbor not in visited:
                count += dfs(neighbor)
        return count
    
    for i in range(1, n+1):
        if i not in visited:
            edge = dfs(i)
            # 여기서 edge-1 을 하는 부분이 변경되었다.
            cost += c_lib*1 + c_road*(edge-1)
    return cost

 

 

복잡하죠.. 저도 어렵네요 ㅠㅠ ㅎㅎㅎ

감사합니다.