[백준] 1260 파이썬(python) : DFS와 BFS - (다른풀이)

1260번 : DFS와 BFS

 

 

다른 사람의 풀이)

from collections import deque
n, m, v = map(int, input().split())
vertex = [ [0]*(n+1) for i in range(n+1) ] #6
for i in range(m):
    a, b = map(int, input().split())
    vertex[a][b] = vertex[b][a] = 1 #1
visit = [0] * (n+1)

def dfs(v):
    visit[v] = 1 #2
    print(v, end=" ")
    for i in range(1, n+1):
        if visit[i] == 0 and vertex[v][i]==1:
            dfs(i) #3

def bfs(v):
    visit[v] = 0 #4
    q = deque()
    q.append(v)
    while q:
        v = q.popleft()
        print(v, end=" ")
        for i in range(1, n+1):
            if visit[i] == 1 and vertex[v][i] == 1: #5
                q.append(i)
                visit[i] = 0
dfs(v)
print()
bfs(v)

 

#6 : 간선이 양방향이기 때문에 서로가 서로를 이어주기 위해서 그리고 예시에서 간선의 최소숫자가 1인것을 생각해서 내부 리스트를 [0]*(n+1)로 한다. [0]*n이면 인덱스 에러가 날것.

#1 : 문제에서 주어지는 간선은 양방향이라 했기에 양방향 노드로 만들어 준다.

#2 : 시작위치 방문처리

#4 : 지나간 자리를 dfs가 1로 지정했기 때문에 bfs는 0을 지나간 자리로 표시(어차피 두 방법 모두 같은 노드만 지나기 때문에 dfs가 0을 1로 만든것을 bfs가 다시 1을 0으로 만드는것이라서 괜찮다.)

#5 : 방문할 수 있고, 간선이 서로 연결되어 있으면 큐에 새로운 노드 넣고 방문처리

 

양방향 노드를 만드는법도 이번에 새롭게 배웠다. 그리고 탈출조건이 없는 재귀함수도 가능하다는걸 알았다.

dfs에서 정점과의 연결관계를 저렇게 표현하는것이 신기하다. 

 

나의 풀이) 22.08.02

import sys
from collections import deque
n, m, v = map(int, sys.stdin.readline().split())
edges = [[ ]*(n+1) for _ in range(n+1) ] #1
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    edges[a].append(b)
    edges[b].append(a)
visit = [False]*(n+1)
arr_dfs, arr_bfs = [], [] #2

def dfs(node):
    visit[node] = True
    arr_dfs.append(node) #3
    for i in sorted(edges[node]): #4
        if visit[i] == False:
            dfs(i)

def bfs(v):
    q = deque()
    visit[v] = True
    q.append(v)
    arr_bfs.append(v) #5
    while q:
        node = q.popleft()
        for i in sorted(edges[node]): #6
            if visit[i] == False:
                visit[i] = True
                q.append(i)
                arr_bfs.append(i) #7

dfs(v)
print(*arr_dfs)
visit = [False]*(n+1) #8
bfs(v)
print(*arr_bfs)

 

#1 : 간선의 연결을 저장할 수 있는 리스트 초기화

#2 : 방문한 순서를 저장하는 리스트 선언

#3 : 출력할 리스트에 추가

#4 : 정렬된 상태에서 반복

#5 : 처음 방문 노드 추가

#6 : 정렬 후 반복

#7 : 출력할 리스트에 추가

#8 : visit 리스트 False로 초기화

 

시간이 지나고 다시 혼자 힘으로 풀어보니 재밌다.