파이썬의 자료구조 - 그래프 문제풀이

그래프 알고리즘 문제풀이 (백준 온라인 저지 18352번)

46번 BFS 탐색 알고리즘을 이용한 인접 리스트 풀이

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

N, M, K, X = map(int, input().split()) # 노드개수, 에지개수, 목표거리, 시작점
A = [[] for _ in range(N+1)] # 그래프 데이터 저장 인접 리스트
answer = [] # 정답 리스트
visited = [-1] * (N+1) # 방문 거리 저장 리스트

def BFS(v) : # BFS 탐색을 최단 거리값을 리스트에 저장
    queue = deque()
    queue.append(v)
    visited[v] += 1 # 거리 저장형태로 1 증가
    while queue : # 큐가 비어있을때
        now_Node = queue.popleft() # 큐에서 노드 데이터 가져오기
        for i in A[now_Node] : 
            if visited[i] == -1 : # 노드에 연결되어 있지만 방문하지 않은 노드
                visited[i] = visited[now_Node] + 1 # visited 리스트값 1 증가
                queue.append(i) # 큐에 노드 삽입

for _ in range(M) : 
    S, E = map(int, input().split())
    A[S].append(E) # A 인접 리스트에 그래프 데이터 저장

BFS(X)

for i in range(N + 1) :
    if visited[i] == K : # 방문 거리가 K인 노드의 숫자를 정답 리스트에 더하기
        answer.append(i)

if not answer :
    print(-1)
else :
    answer.sort()
    for i in answer :
        print(i) # 정답 리스트 정렬하고 출력

그래프 알고리즘 문제풀이 (백준 온라인 저지 1717번)

50번 집합 표현하기

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
parent = [0] * (N+1) # 대표 노드 저장 리스트

def find(a) : 
    if a == parent[a] : # a가 대표 노드면 리턴
        return a 
    else : # a의 대표 노드값을 find(parent[a])값으로 저장 -> 재귀 함수 형태
        parent[a] = find(parent[a])
        return parent[a]

def union(a,b) :
    a = find(a) # a와 b의 대표 노드 찾기
    b = find(b)
    if a != b : # 두 원소의 대표 노드끼리 연걸
        parent[b] = a

def checkSame(a,b) : # 두 원소 같은 집합 확인
    a = find(a)
    b = find(b)
    if a == b : # 두 대표 노드 같으면 true
        return True
    return False

for i in range(0, N+1) :
    parent[i] = i # 대표 노드를 자기 자신으로 초기화

for i in range(M) :
    question, a, b = map(int, input().split())
    if question == 0 : # 질문이 0이면
        union(a, b) # 집합 합치기 (union 연산)
    else :
        if checkSame(a, b) : # 같은 집합 원소인지 확인하고 결과값 출력
            print("YES")
        else:
            print("NO")