[백준/Python] 1260번(DFS, BFS)_DFS와 BFS

📌문제 유형

DFS, BFS(실버 2)

 

📌문제

1260번: DFS와 BFS

 

📌나의 문제풀이

from collections import deque

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

maps = [[] for _ in range(n+1)]
n_set = []
for _ in range(m):
    a,b = map(int, input().split())
    maps[a].append(b)
    maps[b].append(a)

    if a not in n_set:
        n_set.append(a)
    if b not in n_set:
        n_set.append(b)

# maps 정렬하기
for i in range(len(maps)):
    maps[i].sort()



def dfs(v):
    # 더 이상 방문할 점이 없는 경우 종료
    # v가 비어있는 경우 종료
    global visited_d

    if n_set == []:
        return 
    
    if maps[v] == []:
        return 
    
    for next in maps[v]:
        if next not in visited_d:
            visited_d.append(next)
            n_set.remove(next)
            dfs(next)
# DFS
visited_d = []
visited_d.append(v)

if v in n_set:
    n_set.remove(v)

dfs(v)
print(*visited_d)

# BFS
visited_b = []
q = deque([])
q.append(v)

while q:
    now = q.popleft()
    visited_b.append(now)

    for n in maps[now]:
        if n not in visited_b and n not in q:
            q.append(n)

print(*visited_b)

 

📌다른사람의 문제풀이

- 2차원 표에서 0,1로 나타냄

N,M,V = map(int,input().split())

#행렬 만들기
graph = [[0]*(N+1) for _ in range(N+1)]
for i in range (M):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1

#방문 리스트 행렬
visited1 = [0]*(N+1)
visited2 = visited1.copy()

#dfs 함수 만들기
def dfs(V):
    visited1[V] = 1 #방문처리
    print(V, end=' ')
    for i in range(1, N+1):
        if graph[V][i] == 1 and visited1[i] == 0:
            dfs(i)

#bfs 함수 만들기
def bfs(V):
    queue = [V]
    visited2[V] = 1 #방문처리
    while queue:
        V = queue.pop(0) #방문 노드 제거
        print(V, end = ' ')
        for i in range(1, N+1):
            if(visited2[i] == 0 and graph[V][i] == 1):
                queue.append(i)
                visited2[i] = 1 # 방문처리

dfs(V)
print()
bfs(V)

 

📌리뷰

- DFS에서 Typeerror 반환하는 이유

• v에 탐색할 그래프 없는 경우
• dfs가 해당 정점에서 탐색 끝난 후, 다시 위로 올라가지 못한 경우

- 이 문제는 DFS에서 인접행렬(2차원)으로 표시하는게 재귀탈출에 용이

- DFS 그래프 표현방식 : 인접행렬, 인접 리스트

[이것이 취업을 위한 코딩테스트다 with 파이썬] Ch.5 DFS/BFS