[코딩테스트 Python3(6)] Graph 그래프

그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조

그래프 종류

1. 방향 그래프 vs. 무향 그래프
2. 다중 그래프 vs. 단순 그래프
3. 가중치 그래프 → 다익스트라

인접 리스트(adjacency list)

• 대칭으로 구성되고, 가운데 대각선은 0으로 표현된다.
• 위와 같은 방식은 0을 명시해야 하다보니 메모리 낭비가 심하다.
• 따라서 아래와 같이 표현한다.

graph = {
	1: [3,5],
    2: [4,5],
    3: [1,5],
    4: [2,5],
    5: [1,2,3,4]
}

암시적 그래프(Implicit graph)

암시적 그래프라는 용어의 의미는 암시적으로 연결이 모두 되어있다고 간주(연결에 대한 부분은 명시하기 않음)하기 때문이다.

그래프 순회 Traversal

그래프 순회란, 그래프 탐색(search)라고도 불리우며 그래프의 각 정점을 방문하는 과정

그래프 순회 방법에는 크게 1) 너비 우선 탐색(BFS) 2) 깊이 우선 탐색(DFS)의 2가지 알고리즘이 있다.

너비 우선 탐색(BFS; Breadth-First search) 그래프 순회

BFS는 시작 노드에서 가까운 vertex 먼저 순회하는 특징이 있다.

from collections import deque

def bfs(graph, start_v):
    visited = [start_v]
    queue = deque(start_v)
    while queue:
    	cur_v = queue.popleft()
        for v in graph[cur_v]:
        	if v not in visited:
            	visited.append(v)
               	queue.append(v)
    return visited
bfs(graph, 'A')

깊이 우선 탐색(DFS; Depth-first search) 그래프 순회

graph = {...}
visited = []

def dfs(cur_v):
    visited.append(cur_v)
    for v in graph[cur_v]:
    	if v not in visited:
        	dfs(v)
dfs('A')

재귀함수로 코드가 실행된다.

https://leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

이런 문제는 암시적 그래프로 생각하고 풀어야 한다.

from collections import deque

def numIslands(grid):
    number_of_islands = 0
    row = len(grid)
    col = len(grid[0])
    visited = [[False]*col for _ in range(row)]
    
    def bfs(x,y):
    	dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1] #상하좌우를 표현 
        #만약 대각선의 경우도 고려한다면, dx = [-1, 1, 0, 0, 1. -1, 1, -1] & dy = [0, 0, -1, 1, 1, -1, -1, 1]
        visited[x][y] = True
        #deque는 바로 값을 넣은채로 선언하면 오류가 발생할 수 있다.
        queue = deque()
        queue.append((x,y))
        while queue:
        	cur_x, cur_y = queue.popeleft()
            for i in range(4):
            	next_x = cur_x + dx[i]
                next_y = cur_y + dy[i]
                if next_x >= 0 and next_x < m and next_y >= 0 and next_y < n:
                	if grid[next_x][next_y] == "1" and not visited[next_x][next_y]:
                    	visited[next_x][next_y] = True
                        queue.append((next_x, next_y))
  
for i in range(m):
    for j in range(n):
    	if grid[i][j] == "1" and not visited[next_x][next_y]:
        	bfs(i, j)
            number_of_islands += 1
            
return number_of_islands

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/

Shortest Path in Binary Matrix - LeetCode

최단거리 문제 → BFS로 푸는 것이 맞다! 왜냐하면 BFS는 가까운 곳부터 방문하기 때문이다!

가까운 곳부터 순차적으로 방문하기 때문에 출발지에서 가장 가까운 곳부터 빠르게 찾을 수 있다. 

BFS는 Queue를 쓴다는 것을 떠올려야 한다.

from collections import deque

def shortestPathBinaryMatrix(grid):
    shortest_path_len = -1
    row = len(grid)
    col = len(grid[0])

    if grid[0][0] != 0 or grid[row-1][col-1] != 0: return -1
    #무한루프에 빠지지 않으려면 이미 방문했다는 것을 표현해야 함
    visited = [[False] * col for _ in range(row)]
    #8가지 방향을 모두 확인한다.
    delta = [(1,0), (-1,0), (0,1), (0,-1), 
             (1,1), (1,-1), (-1,1), (-1,-1)]
	#deque는 선언할 때 초기화하면 안되고, 선언하고 그 다음에 값을 초기화한다.
    queue = deque()
    queue.append((0,0,1))
    visited[0][0] = True

    while queue:
        cur_r, cur_c, cur_len = queue.popleft()
        #목적지에 도착했을 때 그 때의 cur_len를 shortest_path_len에 저장하면 된다.
        if cur_r == row - 1 and cur_c == col - 1:
            shortest_path_len = cur_len
            break
        #연결되어 있는 vertex 확인하기
        for dr, dc in delta:
            next_r = cur_r + dr
            next_c = cur_c + dc
            if row > next_r and next_r >= 0 and col > next_c and next_c >= 0:
                if grid[next_r][next_c] == 0 and not visited[next_r][next_c]:
                    queue.append((next_r, next_c, cur_len + 1))
                    visited[next_r][next_c] = True

        return shortest_path_len

https://leetcode.com/problems/keys-and-rooms/

Keys and Rooms - LeetCode

머리 깨지는군! 

DFS로 문제로 해결한다. 

def canVisitAllRooms(rooms):
	visited = [False] * len(rooms) #5번방 방문 안했네? => False // True
    
    # v에 연결되어 있는 모든 vertex 방문할거다.
    def dfs(v):
    	visited[v] = True
        for next_v in rooms[v]:
        	#in 연산자는 강력하다 but 리스트에서 in을 쓰면 시간복잡도가 너무 커진다.
        	if visited[next_v] == False:
            	dfs(next_v)
    dfs(0)
    
    if len(visited) == len(rooms):
    	return True
    else:
    	return False
        
    
    return visited