그래프-기초

이론

📖 그래프
노드와 에지로 구성된 집합.

📖 노드와 에지
노드(node) : 데이터를 표현하는 단위.
에지(edge) : 노드를 연결하는 부분.

📖 그래프 구현 방법.

• 에지 리스트(edge list)
  에지를 중심으로 그래프를 표현하는 것.
  리스트에 출발노드와 도착노드 (+가중치)를 저장하여 에지를 표현한다.
  노드사이의 최단거리를 구하는 벨만-포드 나 최소신장트리를 찾는 크루스칼 알고리즘에 사용하면, 노드중심알고리즘에는 잘 사용되지 않는다.

• 인접행렬
  2차원 리스트를 자료구조로 이용하여 그래프를 표현한다.

• 인접리스트
  파이썬의 리스트를 이용하여 그래프를 표현한다.
  그래프를 구현하는 다른 방법에 비해 복잡한 편이지만, 노드와 연결된 에지를 탐색하는 시간이 뛰머나며, 노드개수가 커도 공간효율이 좋아 메모리 초과 에러가 잘 발생되지 않는다.

문제풀이

📖 백준 18352 (🔗백준 18352 문제)

✏ 그래프 , BFS

✏ 모든 도로의 거리가 1이므로 가중치가 없는 인접리스트 사용.

# 그래프, BFS
# 모든 도로의 거리가 1 -> 가중치 없는 인접리스트 사용.
# arr -> 인접리스트 , visit=방문리스트

from collections import deque
import sys
input=sys.stdin.readline

n,m,k,x=map(int,input().split())
arr=[[] for i in range(n+1)]
visit=[-1]*(n+1)
result=[]

#bfs
def bfs(v):
    queue=deque()
    queue.append(v)
    visit[v]+=1
    while queue:
        now=queue.popleft()
        for i in arr[now]:
            if visit[i]==-1:
                visit[i]=visit[now]+1
                queue.append(i)

#인접리스트 데이터 저장
for i in range(m):
    a,b=map(int,input().split())
    arr[a].append(b)

#시작점 : x
bfs(x)

for i in range(n+1):
    if visit[i]==k:
        result.append(i)

result.sort()

if not result:
    print(-1)
else:
    for i in result:
        print(i)

📖 백준 1325 (🔗백준 1325 문제)

📍 시간초과 문제 발생... -> pypy3로 제출

(다시 코드 수정해서 업로드 할 예정...ㅠㅠ)

📖 백준 1707 (🔗백준 1707 문제)

✏ 이분그래프 : 각 집합에 속한 노드끼리 서로 인접하지 않는 두 집합으로 그래프의 노드를 나눌 수 있는 그래프.

✏ 트리의 경우 항상 이분그래프가 되며, 사이클이 발생할 시 이분그래프가
불가능하다.

✏ DFS 수행 시, 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집할일 때 이분그래프가 아니다.

✏ 시간복잡도를 고려하여 이분그래프가 아니라고 판별 시 break를 걸어 탐색을 종료하고 결과를 출력한다.

# 그래프, 이분그래프
# dfs
# dfs 수행 시 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합일 경우, 이분그래프가 아니다.
# 이분 그래프가 아닌 것으로 판별시 시간초과를 고려해서 다음노드는 탐색하지 않도록 break를 걸어준다.

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

k=int(input())
bool=True

def dfs(node):
    global bool
    visit[node]=True
    for i in arr[node]:
        # 아직 방문하지 않은 노드
        if not visit[i]:
            #현재 노드랑 다른 집합으로 노드집합 저장하기.
            check[i]=(check[node]+1)%2
            dfs(i)
        # 방문한 노드지만, 현재 노드와 같은 집합
        elif check[i]==check[node]:
            bool=False

for i in range(k):
    v,e=map(int,input().split())
    arr=[[] for i in range(v+1)]
    visit=[False]*(v+1)
    check=[0]*(v+1)   # 집합 저장 리스트
    bool=True

    for j in range(e):
        start,end=map(int,input().split())
        arr[start].append(end)
        arr[end].append(start)

    for m in range(1,v+1):
        if bool:
            dfs(m)
        else:
            break

    if bool:
        print("YES")
    else:
        print("NO")
        

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준