백준_1260 (BFS와 DFS_뼈대문제_graph 만들기_스택과 deque)

• 링크 : https://www.acmicpc.net/problem/1260

''' 내가 푼 - 주의) 문제는 작은 번호부터 방문함 => 노드 안에서 sort()해야함 '''
from collections import deque

#---------------------------------------------------------------------#
def DFS(check, graph, v):
    check[v] = True               # 일단 체크
    print(v, end = ' ')
                                   # (중요) 재귀 호출 -> loop 사용한다
    for i in graph[v]:            # (중요) v노드의 이웃만 가져온다
        if check[i] == False:     # (중요) v노드의 이웃을 방문 안했다면
            DFS(check, graph, i)
#---------------------------------------------------------------------#
            
def BFS(check, graph, start):
    que = deque([start])            # (중요) BFS는 큐를 만든다
    check[start] = True            
    
    while que:                     # (중요) 재귀 호출 아니다 -> loop만 사용한다
        v = que.popleft()
        print(v, end = ' ')
        
        for i in graph[v]:
            if not check[i]:
                que.append(i)        # (중요) 방문 안한 노드의 이웃 전체 넣어줌
                check[i] = True     # (중요) 넣은건 바로 체크
#---------------------------------------------------------------------#

n, m, v = map(int, input().split())  
arr = [list(map(int, input().split())) for _ in range(m)]  

check = [False] * (n+1)             # (중요) False로 만들 것

# Create Graph (내가 만듦)
graph = [[] for _ in range(n+1)]
for i in range(len(arr)):
    graph[arr[i][0]].append(arr[i][1])
    graph[arr[i][1]].append(arr[i][0])

# 백준 1260의 조건용
for i in range(len(graph)):
    graph[i].sort()
#---------------------------------------------------------------------#

DFS(check, graph, v)
print()
check = [False] * (n+1)            # (중요) 초기화 해줘야 한다......
BFS(check, graph, v)

''' 다른 사람 코드 (블로그) - 나랑 비슷함 '''
import sys
from collections import deque
input=sys.stdin.readline

n,m,start=map(int,input().split())
visited=[False]*(n+1)

graph=[[] for _ in range(n+1)]


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

for i in range(len(graph)):
    graph[i].sort()

def dfs(start):
    print(start,end=' ')
    visited[start]=True
    for i in graph[start]:
        if not visited[i]:
            dfs(i)
            visited[i]=True

def bfs(start):
    q=deque([start])
    visited[start]=True
    while q:
        now=q.popleft()
        print(now,end=' ')
        for i in graph[now]:
            if not visited[i]:
                q.append(i)
                visited[i]=True
dfs(start)
visited=[False]*(n+1)
print()
bfs(start)

''' 동빈나 - 노드 안에서 sort()하지 않을 경우는 이런식으로 sort()만 뺀다고 생각하면 될듯 '''
def dfs(check, graph, v):
    check[v] = True
    print(v, end=' ')
    
    for i in graph[v]:
        if check[i] == False:
            dfs(check, graph, i)
          
        
n, m, v = map(int, input().split())  
arr = [list(map(int, input().split())) for _ in range(m)]  

check = [False] * (n+1)

# Create Graph (내가 만듦)
graph = [[] for _ in range(n+1)]
for i in range(len(arr)):
    graph[arr[i][0]].append(arr[i][1])
    graph[arr[i][1]].append(arr[i][0])
            
dfs(check, graph, v)