DFS/BFS

인접 리스트(리스트 활용), 재귀DFS 큐BFS 풀이

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(100000)

N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, len(graph)):
    graph[i] = sorted(graph[i])

visited = [0] * (N+1)

def DFS(node):
    visited[node] = 1
    print(node, end=" ")

    for v in graph[node]:
        if visited[v] == 0:
            DFS(v)


def BFS(node):
    q = deque()
    q.append(node)
    visited[node] = 1

    while q:
        v = q.popleft()
        print(v, end=" ")

        for i in graph[v]:
            if visited[i] == 0:
                q.append(i)
                visited[i] = 1



DFS(V)
print()
visited = [0] * (N+1)

BFS(V)

인접 행렬, 재귀DFS 큐BFS 풀이

import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

N, M, V = map(int, input().split())
graph = [[0]*(N+1) for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

def DFS(v):
    visited[v] = 1
    print(v, end=" ")

    for i in range(1, N+1):
        if(visited[i] == 0 and graph[v][i] == 1):
            DFS(i)


def BFS(v):
    q = deque()
    q.append(v)
    visited[v] = 1

    while q:
        v = q.popleft()
        print(v, end=" ")

        for i in range(1, N+1):
            if (visited[i] == 0 and graph[v][i] == 1):
                q.append(i)
                visited[i] = 1

visited = [0]*(N+1)
DFS(V)
print()

visited = [0]*(N+1)
BFS(V)

인접 행렬, 스택DFS 큐BFS 풀이

import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

N, M, V = map(int, input().split())
graph = [[0]*(N+1) for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

def DFS(v):
    stack = [v]

    while stack:
        v = stack.pop()
        if visited[v]:
            pass
        else:
            visited[v] = 1
            print(v, end=" ")

            for i in range(N, 0, -1):
                if graph[v][i]:
                stack.append(i)

def BFS(v):
    q = deque()
    q.append(v)
    visited[v] = 1

    while q:
        v = q.popleft()
        print(v, end=" ")

        for i in range(1, N+1):
            if (visited[i] == 0 and graph[v][i] == 1):
                q.append(i)
                visited[i] = 1

visited = [0]*(N+1)
DFS(V)
print()

visited = [0]*(N+1)
BFS(V)

인접 리스트(딕셔너리, 셋 활용) 재귀DFS 큐BFS 구현(visited 0과 1 활용)

# 시작점과 연결된 노드가 하나도 없는 경우, 시작점을 키로 조회할 때 오류가 발생하므로 예외처리 필요!

import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

N, M, V = map(int, input().split())
graph = {}

for i in range(M):
    a, b = map(int, input().split())

    if a not in graph:
        graph[a] = set([b])
    else:
        graph[a].add(b)

    if b not in graph:
        graph[b] = set([a])
    else:
        graph[b].add(a)

for i in graph.keys():
    graph[i] = sorted(list(graph[i]))

visited = [0] * (N+1)

def DFS(node):
    visited[node] = 1
    print(node, end=" ")

    try:
        for v in graph[node]:
            if visited[v] == 0:
                DFS(v)
    except:
        return

def BFS(node):
    q = deque()
    q.append(node)
    visited[node] = 1

    while q:
        v = q.popleft()
        print(v, end=" ")
        try:
            for i in graph[v]:
                if visited[i] == 0:
                    q.append(i)
                    visited[i] = 1
        except:
            return

DFS(V)
print()

visited = [0] * (N+1)
BFS(V)

인접 리스트(딕셔너리, 셋 활용) 재귀DFS 큐BFS 구현(visited에 탐색 원소 담기)

import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

N, M, V = map(int, input().split())
graph = {}

for i in range(M):
    a, b = map(int, input().split())

    if a not in graph:
        graph[a] = set([b])
    else:
        graph[a].add(b)

    if b not in graph:
        graph[b] = set([a])
    else:
        graph[b].add(a)

for i in graph.keys():
	graph[i] = sorted(list(graph[i]))

visited = set()


def DFS(node):
    visited.add(node)
    print(node, end=" ")

    try:
        for v in graph[node]:
            if v not in visited:
            	DFS(v)
    except:
    	return

def BFS(node):
    q = deque()
    q.append(node)
    visited = set()

    while q:
        v = q.popleft()
        if v not in visited:
            visited.add(v)
            print(v, end=" ")

    try:
        q.extend(sorted(list(set(graph[v]) - visited)))
    except:
        return

DFS(V)
print()

visited = [0] * (N+1)
BFS(V)

인접 리스트(딕셔너리, 셋 활용) 스택DFS 큐BFS 구현(visited에 탐색 원소 담기)

import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

N, M, V = map(int, input().split())
graph = {}

for i in range(M):
    a, b = map(int, input().split())

    if a not in graph:
        graph[a] = set([b])
    else:
        graph[a].add(b)

    if b not in graph:
        graph[b] = set([a])
    else:
        graph[b].add(a)

for i in graph.keys():
	graph[i] = sorted(list(graph[i]))


def DFS(node):
    visited = set()
    stack = [node]
    
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.add(v)
            print(v, end=" ")

        try:
        	stack += reversed(sorted(list(set(graph[v]) - visited)))
        except:
        	return


def BFS(node):
    q = deque()
    q.append(node)
    visited = set()

    while q:
        v = q.popleft()
        if v not in visited:
            visited.add(v)
            print(v, end=" ")

    try:
    	q.extend(sorted(list(set(graph[v]) - visited)))
    except:
    	return

DFS(V)
print()

visited = [0] * (N+1)
BFS(V)