백준 1260

yellowsubmarine372·2023년 2월 1일
0

백준

목록 보기
4/38

< DFS와 BFS 프로그램>

난이도 : 실버2

  1. 백준 문제
    백준 1260

  2. 코드 알고리즘

  1. 코드
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
n, m, v = map(int,input().split())
from collections import deque
myQueue = deque()
A=[[] for i in range(n+1)]
check_list_d=[0]*(n+1)
check_list_b=[0]*(n+1)

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

for i in range(n+1):
    A[i].sort()

def DFS(i):
    print(i, end=' ')
    check_list_d[i]=1
    for j in A[i]:
        if not check_list_d[j]:
            DFS(j)
#stack을 굳이 구현할 필요가 없음
#원래의 A로부터 출력만 하면 선입후출의 구조 형성
#처음 for문에서 다 해결 됨 -> for 문 안의 각각 경우에 다 깊이 들어가므로
#for문 1번에서 다 해결
DFS(v)
print()

def BFS(i):
    myQueue.append(v)
    check_list_b[i]=1
    while myQueue:
        id=myQueue.popleft()
        print(id, end=' ')
        for j in A[id]:
            if not check_list_b[j]:
                myQueue.append(j)
                check_list_b[j]=1
#재귀 꼴을 선언 안함
#각각의 노드에 파고들을 필요없음
#각 입력된 한 줄에서만 해결한 후 다음 줄로 넘어가는 경우이므로
BFS(v)
profile
for well-being we need nectar and ambrosia

0개의 댓글