[백준] 1260 DFS와 BFS

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

문제 설명

문제는 기본적인 DFS와 BFS를 물어보는 문제이다. 이미 이전에도 풀어본 적이 있지만 코딩테스트용 언어를 변경했기에 처음부터 시작한다는 마음으로 시도하고 있다. 문제 자체의 난이도는 크게 높지 않다. 

코드에 주석을 달아놓았기에 재귀함수나 큐에 대한 지식이 있다면 크게 문제되지 않을 것이다.

 

코드

from collections import deque

def BFS(v):
    q = deque() #큐 생성
    q.append(v) #큐에 시작점 추가
    visit1[v] = 1 # 큐에 들어간 시작점 방문했다고 표시

    while q:
        v = q.popleft() #큐에 존재하는 노드를 pop
        print(v, end = " ") #현재 방문한 노드를 표시
        for i in range(1 ,n+1): #현재 위치한 노드들과 연결될수 있는 모든 노드들을 탐색
            if visit1[i] == 0 and graph[v][i] == 1: #만약 현재의 노드와 연결되어 있고 미방분 상태인 경우
                q.append(i) #큐에 넣음
                visit1[i] = 1 #방문했다고 표시


def DFS(v):
    visit2[v] = 1 #현재 위치한 노드를 방문했다고 표시
    print(v, end = " ") #노드 출력
    for i in range(1,  n+1): #현재 위치와 연결되어 있을가능성이 있는 노드 전부 탐색
        if visit2[i] == 0 and graph[v][i] == 1: # 만약 현재의 노드와 연결되어 있고 미방문한 노드가 존재하는 경우
            DFS(i) #재귀함수 탐색

n, m, v = map(int ,input().split())

graph = [ [0] * (n+1) for _ in range(n+1) ] #그래프 초기화
visit1 = [0] * (n+1)
visit2 = [0] * (n+1)

for _ in range(m): #그래프 생성
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

DFS(v)
print()
BFS(v)

 

참고

1 https://velog.io/@hamfan524/%EB%B0%B1%EC%A4%80-1260%EB%B2%88-Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 1260번-(Python 파이썬) - Bfs, Dfs

2 https://dongdongfather.tistory.com/72

[파이썬 기초] 스택과 큐의 기능을 한번에 deque