[파이썬]백준 1260 DFS와 BFS

링크

백준 1260 DFS와 BFS

dfs와 bfs만 구현하면 되는 문제이나 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고 라는 조건때문에 약간 신경을 써줘야한다.
나는 인접그래프 리스트를 정렬해주는 방법으로 이를 해결했다.
여태까진 방문을 했는지 안했는지만 따지다가 경로를 받아야하니 조금 헤맸다.
분명히 더 이쁘고 가독성 좋게 코드를 짤 수 있을텐데 아직 실력이 부족한것 같다. 특히 dfs를 많이 연습해봐야 할 것 같다.

정답 코드

from collections import deque

def dfs(s):
    visit = [0] * (N + 1)
    search = []
    stack = []
    stack.append(s)
    visit[s] = 1
    while stack:
        v = stack.pop()
        for w in g[v]:
            if visit[w] == 0:
                stack.append(w)
        visit[v] = 1
        if v not in search: #마지막요소가 2개씩 들어가는 일이 발생해서 이를 막아줌
            search.append(v)
    return search

def bfs(s):
    visit = [0] * (N + 1)
    search = [V]
    q = deque()
    q.append(s)
    visit[s] = 1
    while q:
        v = q.popleft()
        for w in g[v]:
            if visit[w] == 0:
                visit[w] = 1
                q.append(w)
                search.append(w)
    return search

#정점 간선 시작점
N, M, V = map(int, input().split())

g = [[] for _ in range(10001)]

for _ in range(M):
    v, w = map(int, input().split())
    g[v].append(w)
    g[w].append(v)

for i in range(M + 1): #dfs는 스택을 사용하므로 reverse 해줘야 작은것부터 꺼내서 탐색함
    g[i].sort(reverse= True)

print(' '.join(map(str, dfs(V))))

for i in range(M + 1): #정점 번호가 작은 것을 먼저 방문하기 위해 연결리스트를 정렬시킴
    g[i].sort()

print(' '.join(map(str, bfs(V))))

알게된 것👨‍💻

• dfs를 구현하는게 아직 많이 어색하다. 연습이 필요하다.