백준 실버2 1260. DFS와 BFS (python)

DFS와 BFS

풀이

dfs와 bfs의 기본적인 코드를 풀이하기 좋은 문제이다.
그런데 난 올바로 했다고 생각했는데 왜 계속 틀렸는지 모르겠다.

우선 보통 재귀를 이용해서 dfs 문제를 풀었는데 난 stack을 이용하기 위해 stack을 이용해서 풀었고, 또한 deque를 사용해서 bfs를 풀었는데 난 deque를 사용하지 않고 풀었다.
(이 문제에선 굳이?)

마음 같아선, pop이 아닌 top 그리고 front, rear를 이용해서 풀고 싶었지만 우선 이 방식으로 되는지 먼저 확인하고 싶었기에 pop과 append를 이용했다.

다음과 같이 풀었다.

1. 노드 개수 N, 간선 개수 M, 시작 노드 V를 입력받고 인접행렬을 만들어준다.
2. dfs 함수와 bfs 함수를 생성
3. dfs는 stack을 이용해서 visited와 함께 찾는 노드에 연결된 노드를 찾아내고 그 노드를 기준으로 계속해서 깊이 우선탐색을 실시
4. bfs는 Q를 이용해서 visited와 함께 찾는 노드에 연결된 노드를 찾아내고 현재 노드를 기준으로 계속해서 너비우선탐색을 실시
5. 각 함수에서 result에 출력될 값을 기록(나중에 유사한 문제 나오면 똑같이 써먹게) 후 이를 이용해서 답을 출력

import sys

N, M, V = map(int, sys.stdin.readline().split())

# 인접행렬 생성
graph = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a][b] = 1
    graph[b][a] = 1


def dfs(V):
    stack = [V]
    visited = [False] * (N+1)
    visited[V] = True
    result = [V]
    while stack:
        node = stack[-1]
        for i in range(1,N+1):
            # 노드랑 연결되어있고, 방문하지도 않은 곳이면
            if graph[node][i] == 1 and not visited[i]:
                stack.append(i)
                result.append(i)      
                visited[i] = True
                # 깊이 우선 탐색이므로 찾았으면 break
                break
        else:
            stack.pop()
    return result

def bfs(V):
    Q = [V]
    visited = [False] * (N+1)
    visited[V] = True
    result = [V]
    while Q:
        node = Q.pop(0)
        for i in range(1, N+1):
            if graph[node][i] == 1 and not visited[i]:
                Q.append(i)
                result.append(i)
                visited[i] = True
                # 너비 우선탐색이니 찾아도 break하지 않고 해당 노드에서 계속 찾게 하기

    return result

answer1 = dfs(V)
answer2 = bfs(V)
print(' '.join(map(str, answer1)))
print(' '.join(map(str, answer2)))

다른 사람 풀이

재귀를 이용해서 dfs를 풀이했다.
재귀를 이용해서 내가 푼 풀이에서의 break를 바로 dfs(i)로 들어가는 방식이 적용되었다고 생각하면 된다.

그래프 또한 인접행렬이 아닌 인접리스트를 사용하였다.

result = []
def dfs(n):
    visited1[n] = True
    print(n, end= ' ')
    for i in graph[n]:
        if not visited1[i]:
            dfs(i)

def bfs(n):
    result = []
    visited = [False]*(N+1)
    queue = [n]
    visited[n] = True
    while queue :
        a = queue.pop(0)
        if a not in result:
            result.append(a)
        for i in graph[a]:
            if not visited[i]:
                queue.append(i)
                visited[a] = True
    return result

import sys
N, M, V = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1) ]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(N+1):
    graph[i].sort()

visited1=[False]*(N+1)
dfs(V)
print()
print(*bfs(V))