[ 그래프 ] 자료구조
1. 개념
1 ) 정의
그래프 : 노드(데이터)간의 연결 관계를 에지(간선)를 통해 나타내는 자료 구조
2 ) 그래프의 특성
* 방향성 : 에지가 노드를 연결할 때 방향을 갖는지 -> 방향 그래프 / 무방향 그래프
* 가중치 : 에지가 노드를 연결할 때 가중치를 갖는지 -> 가중치 그래프 / 무가중치 그래프
3 ) 그래프의 표현 방법
( 1 ) 에지 리스트 : 에지 중심으로 그래프 표현
-> 첫번째 열에 출발 노드, 두번째 열에 도착 노드 저장
장점 : 구현하기 쉽다
단점 : 특정 노드와 관련되어 있는 에지를 탐색하기 어렵다
활용 : 벨만-포드 알고리즘, 크루스칼 알고리즘( 최소 신장 트리 찾는 알고리즘 )
( 2 ) 인접 행렬 : 노드 중심으로 그래프 표현
-> 2차원 리스트를 이용해 ( 출발노드, 도착노드 ) 칸에 1 혹은 가중치 저장
장점
- 구현하기 쉽다
- 노드간 인접 여부와 가중치 확인이 쉽다
단점
- 특정 노드와 관련되어 있는 에지를 탐색하려면 n번 접근해야 하므로 시간복잡도가 느리다
- 노드 개수에 비해 에지가 적으면 공간 효율성이 떨어진다
( 3 ) 인접 리스트 : 노드 개수만큼 리스트를 선언한 뒤 특정 노드와 인접한 노드를 저장
장점
- 노드와 연결된 에지를 빠르게 탐색할 수 있다
- 공간 효율성이 좋다
단점
- 구현하는 게 복잡하다
2. 문제
# 1 특정 거리의 도시 찾기 - 백준 18352번
https://www.acmicpc.net/problem/18352
18352번: 특정 거리의 도시 찾기
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개
www.acmicpc.net
import sys
from collections import deque
input = sys.stdin.readline
n, m, k, x = map(int, input().split())
node = [[] for i in range(n)]
visited = [-1 for i in range(n)]
ans = []
for i in range(m):
a, b = map(int, input().split())
node[a-1].append(b)
def BFS(x, d):
queue = deque()
queue.append(x)
visited[x-1] = 0
while queue:
a = queue.popleft()
for i in node[a-1]:
if visited[i-1] == -1:
visited[i-1] = visited[a-1] + 1
queue.append(i)
BFS(x, 0)
for i in range(len(visited)):
if visited[i] == k:
ans.append(i+1)
ans.sort()
if len(ans) == 0:
print(-1)
else:
for i in ans:
print(i)
# 2 효율적으로 해킹하기 - 백준 1325번
https://www.acmicpc.net/problem/1325
1325번: 효율적인 해킹
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한
www.acmicpc.net
import sys
import copy
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
node = [[] for i in range(n)]
truth = [0 for i in range(n)]
M = 0
# 인접 리스트 생성
for i in range(m):
a, b = map(int, input().split())
node[a-1].append(b)
# BFS 실행
def BFS(v):
queue = deque()
queue.append(v)
visited[v-1] = True
while queue:
a = queue.popleft()
for i in node[a-1]:
if not visited[i-1]:
queue.append(i)
visited[i-1] = True
# 신뢰도 증가
truth[i-1] += 1
# 모든 노드를 한번씩 시작 노드로 두고 BFS 실행
for i in range(n):
visited = [False for i in range(n)]
BFS(i)
for i in range(len(truth)):
if M < truth[i]:
M = truth[i]
for i in range(len(truth)):
if truth[i] == M:
print(i+1, end = ' ')
그래프의 깊이 관련된 문제를 풀 때는 BFS를 이용해야 할 듯...
처음에는 DFS로 했는뎅 안 풀린디야..
시작 노드와 연결된 에지마다 깊이가 다 달라서 BFS로 해야 되는 건가?
공부하자..
# 3 이분 그래프 - 백준 1707번
https://www.acmicpc.net/problem/1707
1707번: 이분 그래프
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에
www.acmicpc.net
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def DFS(v):
global ans
visited[v-1] = True
for i in node[v-1]:
if not visited[i-1]:
if group[v-1] == "A":
group[i-1] = "B"
else:
group[i-1] = "A"
DFS(i)
else:
if group[v-1] == group[i-1]:
ans = False
T = int(input())
for i in range(T):
v, e = map(int, input().split())
node = [[] for _ in range(v)]
visited = [False for _ in range(v)]
group = [0 for _ in range(v)]
global ans
ans = True
for j in range(e):
a, b = map(int, input().split())
node[a-1].append(b)
node[b-1].append(a)
for t in range(v):
DFS(t+1)
if not ans:
print("NO")
break
if ans:
print("YES")43퍼에서 계에에에속 틀리는 코드..... 아아아ㅏ앙ㄱ 너무 어렵다
비연결 그래프에서 틀리는 건가??
책에 나온 코드..
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(sys.stdin.readline())
IsEven = True
def DFS(node) :
global IsEven
visited[node] = True
for i in A[node]:
if not visited[i]:
check[i] = (check[node]+1)%2
DFS(i)
# 이미 방문한 노드가 현재 내 노드와 같은 집합이면 이분 그래프 아님
elif check[node] == check[i]:
IsEven = False
for _ in range (N):
V, E = map(int, input().split())
A = [[] for _ in range(V + 1)]
visited = [False] * (V + 1)
check = [0] * (V + 1)
IsEven = True
for i in range(E):
Start, End = map(int, sys.stdin.readline().split())
A[Start].append(End)
A[End].append(Start)
for i in range(1, V + 1):
if IsEven:
DFS(i)
else:
break
if IsEven:
print ("YES")
else:
print ("NO")
# 4 물통 - 백준 2251번
https://www.acmicpc.net/problem/2251
2251번: 물통
각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부
www.acmicpc.net
세상에... 감도 안 잡히는군...ㅎㅎㅎㅎㅎ
from sys import stdin
from collections import deque
# Sender와 Receiver 두 리스트를 이용하여 6가지 이동 케이스를 간편하게 정의할 수 있다
# 6가지 이동 케이스(A->B, A->C, B->A, B->C, C->A, C->B)
# 0, 1, 2 는 각각 A, B, C 의미
Sender = [0,0,1,1,2,2]
Receiver = [1,2,0,2,0,1]
now = list(map(int,stdin.readline().split()))
visited = [[False for _ in range(201)] for _ in range(201)]
answer = [False] * 201
def BFS():
queue = deque()
queue.append([0,0])
visited[0][0] = False
answer[now[2]] = True
while queue:
NowNode = queue.popleft()
A = NowNode[0]
B = NowNode[1]
C = now[2]-A-B
for k in range(6):
next = [A,B,C]
next[Receiver[k]] += next[Sender[k]]
next[Sender[k]] = 0
# 물이 넘치는 경우
if next[Receiver[k]] > now[Receiver[k]] :
# Receiver가 꽉 차고 남은 물 Sender에 넣기
next[Sender[k]] += next[Receiver[k]] - now[Receiver[k]]
next[Receiver[k]] = now[Receiver[k]]
if not visited[next[0]][next[1]]:
visited[next[0]][next[1]] = True
queue.append([next[0],next[1]])
# A가 빌 때
if next[0] == 0:
answer[next[2]] = True
BFS()
for i in range(201):
if answer[i]:
print(i,end = ' ')