그래프

그래프

그래프는 과연 자료구조의 꽃이자 핵이라 할 수 있다.
DFS, BFS, TREE, 다익스트라, 크루스칼, TSP, 해밀턴 이런 모든 알고리즘들이 전부 그래프에서 나온것이기 때문이다.

그러면 그래프를 시작해보겠다.

그래프의 종류

무방향 그래프 (Undirected Graph)

• 방향성이 없는 그래프이다. 다음과 같이 표현한다
  V(g1) = {A, B, C, D}
  E(g1) = {(A, B), (A, C), (A, D), (B, C), (C, D)}

방향 그래프 (directed graph)

• 방향성이 있는 그래프이다. 다음과 같이 표현한다
  V(g1) = {A, B, C}
  E(g1) = {<A, B>, <B, A>, <B, C>}

가중치 그래프 (weighted graph)
간선에 가중치나 무게가 할당 된 그래프이다.

부분 그래프 (sub graph)
다른 그래프 G를 구성하는 정점의 집합 V(G)와 간섭의 집합 E(G)의 부분집합으로 이루어진 그래프이다.

그래프 용어

인접 정점 : 간선에 의해 직접 연결된 정점이다
정점의 차수 : 정점에 연결된 간선의 차수이다
경로 : 간선을 따라 갈 수 있는 길이다

연결그래프 : 모든 정점 사이에 경로가 존재하는 그래프이다
트리 : 사이클을 가지지 않는 연결그래프이다
완전그래프 : 모든 정점 간에 간선이 존재하는 그래프이다

그래프의 표현

그래프를 표현하는 방식은 크게 두가지가 있는데
1. 인접행렬 2. 인접리스트 이다.

# 인접행렬
n, m = input().split()
m, n = int(m), int(n)
adjMatrix = [[0 for _ in range(n)] for _ in range(n)]
adjList1 = [None for _ in range(n)]
adjList2 = [[] for i in range(n)]
visited = [False for _ in range(n)]  # 'white'

for i in range(m):
    u, v = input().split()
    u, v = int(u), int(v)
# adjacency matrix
    adjMatrix[u][v] = 1
    adjMatrix[v][u] = 1
print(adjMatrix)

# 인접리스트
class Node:
    def __init__(self, vertex):
        self.vertex = vertex
        self.link = None

class Graph:
    def __init__(self, size):
        self.adjList = [None] * size
        self.size = size

    def insertEdge(self, v1, v2):
        newNode = Node(v2)
        newNode.link = self.adjList[v1]
        self.adjList[v1] = newNode
        # in case of undirected graph

        newNode = Node(v1)
        newNode.link = self.adjList[v2]
        self.adjList[v2] = newNode

    def printGraph(self):
        for v in range(self.size):
            print(v, end=': ')
            current = self.adjList[v]
            while current is not None:
                print(current.vertex, end=' ')
                current = current.link
            print()

def main():
    n, m =  input().split()
    n, m = int(m), int(n)
    g = Graph(n)
    for i in range(m):
        v1, v2 = input(). split()
        v1, v2 = int(v1), int(v2)
        g.insertEdge(v1,v2)
    g.printGraph()

if __name__ == '__main__':
    main()

# 리스트 of 리스트
n, m = input().split()
m, n = int(m), int(n)
adjList2 = [[] for i in range(n)]
visited = [False for _ in range(n)] # 'white'

for i in range(m):
    u, v = input().split()
    u, v = int(u), int(v)

# adjacenct list2
    adjList2[u].append(v)
    adjList2[v].append(u)
print(adjList2)

그래프의 탐색

DFS

def dfs3(adjList2, n, v, visited):
    visited[v] = True
    print(v, end = ' ')

    for i in range(len(adjList2[v])):
        w = adjList2[v][i]
        if visited[w] == False:
            dfs3(adjList2, n, w, visited)

n, m = input().split()
m, n = int(m), int(n)
adjList2 = [[] for i in range(n)]
visited = [False for _ in range(n)] # 'white'

for i in range(m):
    u, v = input().split()
    u, v = int(u), int(v)

# adjacenct list2
    adjList2[u].append(v)
    adjList2[v].append(u)
print(adjList2)
print('dfs at 0 using adjacency list : ')
dfs3(adjList2, n, 0, visited)
print()

BFS

from collections import deque


def bfs(graph, start, visited):
    # 시작 값으로 큐 초기화
    queue = deque([start])
    # 시작 노드 방문 처리
    visited[start] = True

    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 방문하지 않은 인접 노드들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


# 각 노드가 연결된 정보를 표현(0번 인덱스는 무시)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
# 각 노드가 방문한 정보를 표현

bfs(graph, 1, visited)


# 1 2 3 8 7 4 5 6

def bfs_maze(x, y):
    # bfs이므로 큐 사용
    queue = deque()
    queue.append((x, y))
    # 큐가 빌 때까지 반복
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 상,하,좌,우 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 공간을 벗어난 경우 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 괴물이 있는 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 +1해서 최단기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단거리 반환
    return graph[n - 1][m - 1]


n, m = map(int, input().split())

graph = []
for i in range(n):
    graph.append(list(map(int, input())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

print(bfs_maze(0, 0))