[백준] 1260. DFS와 BFS

# import sys
# sys.stdin = open("input.txt", "r")
from collections import deque

# DFS
def DFS(now):
    global N
    print(now, end=' ')
    for next in range(1, N+1):
        if next not in adj[now]: continue
        if visited[next] == 1: continue
        visited[next] = 1
        DFS(next)

# BFS
def BFS(s):
    global N
    q = deque()
    q.append(s)
    while q:
        now = q.popleft()
        print(now, end=' ')

        for next in range(1, N+1):
            if next not in adj[now]: continue
            if visited[next] == 1: continue
            visited[next] = 1
            q.append(next)


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

for i in range(M):
    n1, n2 = map(int, input().split())
    adj[n1].append(n2)
    adj[n2].append(n1)

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

코드트리 알고리즘으로 기초를 다시 정리하고 나서 알고리즘 문제에 다시 도전해보기로 했다!

BFS와 DFS 방법론만 알고 있으면 쉽게 풀 수 있는 문제고, 처음에 adj라는 2차원 배열을 전부 0으로 먼저 넣어놓는 방식을 생각했다가, 필요한 값만 각 행에 넣어버리는 방법으로 바꾸었다.(이게 메모리를 덜 차지하는 방법일 듯)

SWEA A형을 목표로 앞으로 열심히 해보자!!