🧚‍♂️알고리즘🧚‍♂️ - 그래프 - 그래프기초

🧚🏻‍♀️그래프🧚🏻‍♀️

노드 : 데이터를 표현하는 단위

에지 : 노드를 연결

---

🧚🏻‍♀️그래프 구현법🧚🏻‍♀️

1. 에지 리스트

에지를 중심으로 그래프 표현

[출발 노드 / 도착 노드 / (가중치가 있을 시) 가중치] 로 표현

오른쪽 리스트가 (가중치 없는)에지리스트

+ 벨만 포드 알고리즘 / 크루스칼 알고리즘 등에 사용(노드 중심 알고리즘엔 잘 사용되지 않음)

---

2. 인접 행렬

노드를 중심으로 그래프 표현

가중치가 존재할 시 1 대신 가중치로 표현

오른쪽 행렬이 인접 행렬

+ 노드 개수에 비해 에지가 적을 때는 비효율적

---

3. 인접 리스트

인덱스 번호의 리스트에 인접한 노드를 다 넣어두기

가중치가 있을 시 [(a,b),(c,d)] 형태로 저장

오른쪽이 (가중치 없는)인접 리스트

+ 젤 편한 듯

---

리스트에 같은 값 쉽게 넣는 방법 ([0,0,0] 예시)
1.  [0]*3
2. [0 for _ in range(3)]

1번은 얕은 복사이므로 2번 추천

+ append로 하나의 리스트 계속 넣기 안됨!! 주소만 들어감(즉 다 똑같아짐)

가중치 주의~!

방향 있는지 주의~!

---

18352번

실버 2

18352번: 특정 거리의 도시 찾기

- BFS 이용(최단 거리이므로)

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

#BFS
from collections import deque #큐 필요
from sys import stdin
N,M,K,X = map(int,stdin.readline().split()) # 도시개수, 도로개수, 거리 정보, 출발도시
# 방문 체크 리스트!
visited = [-1 for _ in range(N+1)] 
Nlist = [[] for _ in range(N+1)]

for i in range(M):
    A, B = map(int,stdin.readline().split())
    Nlist[A].append(B) # 단방향

def BFS(v):
    Myqueue = deque()
    Myqueue.append(v)
    visited[v] = 0
    while(Myqueue): # 마이큐에 값이 있을 때까지
        NowNode = Myqueue.popleft() #선입선출
        for k in Nlist[NowNode]:
            if visited[k] == -1:
                visited[k] = visited[NowNode] + 1
                Myqueue.append(k)
BFS(X) 

result = []
for i in range(N+1):
    if visited[i] == K:
        result.append(i)

if result:
    result.sort()
    for cha in result:
        print(cha)
else:
    print(-1)

---

1325번

실버 1

오호..예전에 실패했었던.. 이독엠티 팀대항전 문제였었나?

1325번: 효율적인 해킹

#BFS
from collections import deque #큐 필요
from sys import stdin
N,M = map(int,stdin.readline().split()) # 컴개수 , 관계
# 관계도
Nlist = [[] for _ in range(N+1)]
realresult = [0 for _ in range(N+1)]

for i in range(M):
    A, B = map(int,stdin.readline().split())
    Nlist[B].append(A) # A가 B를 신뢰하므로 B를 해킹했을 때-> A도 해킹 가능

def BFS(v):
    Myqueue = deque()
    Myqueue.append(v)
    visited[v] = True
    while(Myqueue): # 마이큐에 값이 있을 때까지
        NowNode = Myqueue.popleft() #선입선출
        for k in Nlist[NowNode]:
            if not visited[k]:
                visited[k] = True
                realresult[i] += 1
                Myqueue.append(k)

for i in range(1, N+1):
    # 방문 체크 리스트 초기화!
    visited = [False for _ in range(N+1)]
    BFS(i) 

rere = max(realresult)

for i in range(N+1):
    if realresult[i] == rere:
        print( i, end = " ")

으엑 파이썬으로는 계속 시간초과난다..

파이파이로 해야함..

느으린 채점..

---

1707번

골드 4

1707번: 이분 그래프

✴️이분 그래프✴️
인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프
모든 간선의 양끝 노드가 다른 색인 그래프
- 그래프가 비연결 그래프인 경우 모든 정점에 대해서 확인하는 작업이 필요
- 탐색을 진행할 때 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아님
- BFS의 경우 같은 깊이에서 정점을 다른 색으로 칠해야 한다면 무조건 이분 그래프가 아님

- 비연결 가능성이 있으므로 모든 노드를 시작으로 탐색해보기

- 탐색하다가 이미 탐색한 노드에 도착했을 때 집합이 다르면 이분 그래프 아님.

from collections import deque #큐 필요
from sys import stdin
K = int(stdin.readline()) #테스트케이스

def BFS(v):
        Myqueue = deque()
        Myqueue.append(v)
        Color[v] = 1
        while(Myqueue): # 마이큐에 값이 있을 때까지
            NowNode = Myqueue.popleft() #선입선출
            for k in Nlist[NowNode]:
                if Color[NowNode] == Color[k]:
                    global result
                    result = False
                    return True
                else:    
                    if Color[k] == 0:
                        Color[k] = -Color[NowNode]
                        Myqueue.append(k)
        return False
    
for _ in range(K):
    V, E = map(int,stdin.readline().split()) # 정점 , 간선
    # 관계도
    Nlist = [[] for _ in range(V+1)]
    # 결과
    result = True

    for i in range(E):
        A, B = map(int,stdin.readline().split())
        Nlist[A].append(B) #양방향
        Nlist[B].append(A)

    # 모든 노드를 시작으로 탐색해보기
    for i in range(1,V+1):
        # 집합 나누기 리스트
        Color = [0 for _ in range(V+1)]
        if BFS(i):
            break

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

시간 초과~~~^^ 찐맞았는지도 잘 모르겠는 코드~~~^^^^^

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")

교재의 코드인데.. 시간복잡도에서 어떤 차이가 있는 거지?

글 읽기 - 시간복잡도계산이란..

---

2251번

골드 5

2251번: 물통

그래프를 역으로 그리는 방식 이용!

노드 : A,B,C의 물 양 상태

한번 바꿀 수 있는 상태를 인접 노드로!

from sys import stdin
from collections import deque

Sender = [0,0,1,1,2,2] # 물 이동 가능한 경우 6가지
Receiver = [1,2,0,2,0,1]
now = list(map(int,stdin.readline().split()))
visited = [[False for _ in range(201)] for _ in range(201)] # A,B의 물양 리스트(최대 200L)
answer = [False] * 201

def BFS():
    queue = deque()
    queue.append([0,0]) # 맨 처음  0,0,c크기
    visited[0][0] = False
    answer[now[2]] = True # A 비어 있음

    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]] : # 넘칠 때
                #넘친 만큼 다시 이전 물통에 넣기
                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]])
                if next[0] == 0: # A 비어 있음
                    answer[next[2]] = True

BFS()

for i in range(201):
    if answer[i]:
        print(i,end = ' ')

리스트 의미 잘 이용해서 써보기 (센더, 리시버 등)

튜플 써보기

 

한 단계씩 변화하는 것 -> 그래프로 이어서 생각해 보기.(탐색이용) ( 이때 경우의 수가 천문학적이지 않아야 함/물컵 3개였던 것처럼)