[지코바] 다른 사람 코드 분석하기 - DFS와 BFS

1. 문제

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

1260번: DFS와 BFS

 

2. 코드 분석

1) 사전작업

import sys

# N(정점 수), M(간선 수), V(시작 정점)를 입력받음
N, M, V = map(int, sys.stdin.readline().split(' '))

# (N+1)x(N+1)의 보드 생성, 0으로 초기화
board = [[0 for _ in range(N+1)] for _ in range(N+1)]

# (N+1)길이의 리스트 생성, 0으로 초기화
vis1 = [0 for _ in range(N+1)]
vis2 = [0 for _ in range(N+1)]

# 간선 수만큼 정점 쌍을 입력 받음
for _ in range(M):
    # strip(): 문자열 양 끝의 공백 제거
    x, y = map(int, sys.stdin.readline().strip().split(' '))
    # 1 2가 입력으로 들어왔으면 보드의 (1, 2), (2, 1)의 값을 1로 
    board[x][y] = 1
    board[y][x] = 1

 

2) DFS

# DFS

stack = list()  #stack이라는 이름의 리스트 선언
stack.append(V)  # stack에 최초 정점 V를 추가
vis2[V] = 1  # vis2 list의 V 인덱스 위치를 1로 둠 (방문한 정점을 체크하는 리스트)

# answer2 리스트를 선언하고 최초 정점 V를 추가
answer2 = list()
answer2.append(V)

while len(stack) != 0:  # stack list가 빌 때까지 반복
	# stack list의 마지막 요소를 x에 할당하고, stack list에서 그 요소를 제거
    x = stack.pop()
    
    for i in range(N+1):  # i: 0 ~ N
    
        # x와 간선으로 연결되어 있으면서, 가장 작은 정점을 찾는 분기문
        if i == x: continue  # i가 직전에 stack list에서 pop한 요소라면 아래 코드를 무시하고 반복 진행
        if vis2[i] == 1 or board[x][i] != 1: continue  # i가 이미 방문한 정점이거나 x와 간선으로 연결되지 않은 정점이라면 아래 코드를 무시하고 반복 진행
        
        # 위 조건을 만족하는 정점을 찾은 경우 처리
        vis2[i] = 1  # i를 방문한 정점으로 표시
        # x와 i를 stack list, answer2에 추가
        stack.append(x)
        stack.append(i)
        answer2.append(i)
        break
        
# 답을 출력
print(' '.join(map(str, answer2)))

 

3) BFS

# BFS

# que list를 선언하고, 최초 정점 V를 리스트에 추가
que = list()
que.append(V)
vis1[V] = 1  # 방문한 정점을 저장하는 리스트 vis1에 최초 정점 방문 표시

# 답을 저장하는 리스트를 선언, 최초 정점을 추가
answer1 = list()
answer1.append(V)

# que가 빌 때까지 반복
while len(que) != 0:
    x = que.pop(0)  # 리스트의 첫번째 요소를 x에 할당, 그 요소를 제거
    for i in range(N+1):
        if i == x: continue
        if vis1[i] == 1 or board[x][i] != 1: continue
        vis1[i] = 1
        # DFS와 달리 기준이 된 정점 x는 다시 기준이 될 수 없으므로 x를 리스트에 추가해주지 않음
        que.append(i)
        answer1.append(i)
        
# 답을 출력
print(' '.join(map(str, answer1)))