[백준 2024/09/25] 1260번 DFS와 BFS

1. 문제

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

 

2. 접근 방법

특정 노드를 방문하는 데 여러 간선이 있으므로 중복적인 방문이 될 수 있다.

또한 dfs와 bfs 결과를 처음 나온 결과 하나만 반환한다.

따라서, 방문을 기록하기 위해서 visited_bfs와 visited_dfs 라는 리스트를 기록해 주었다.

 

dfs의 경우 처음 stack으로 풀고 싶었지만, 실패해서 재귀로 풀게 되었다.

스택으로 처리한 경우가 있을까 하여 질문 게시판을 확인하였고 아래와 같은 답변을 찾을 수 있었다.

https://www.acmicpc.net/board/view/128850

 

recursion vs. stack

- 재귀 w. 전역

def dfs(node):
    visited_dfs.append(node)

    for i in sorted(edges[node]):
        if i not in visited_dfs:
            dfs(i)

 

재귀에 대한 dfs 코드는 깔끔하다. 방문하지 않았다면 dfs 함수를 호출해 준다.

return 문을 사용하지 않고 전역 변수로 선언한 visited_dfs를 사용해 주었다. 

4개의 노드를 방문하고 난 후에는, 모든 노드가 if i not in visited_dfs를 통과하지 못하게 되고 함수가 끝나게 된다.

이 부분이 내가 일반적으로 코딩하던 부분과 다른 부분이었다.

일반적으로 dfs를 구성할 때는, visited를 해당 가지에서만 수정을 하고 넘겨줘야 했던 부분이 있었다.

하지만 이번 dfs는 처음 결과만 출력하면 되므로 visited를 전역적으로 사용했어야 했다.

 

- 재귀 w. local

def dfs(node, visited_dfs):
    visited_dfs.append(node)  # 현재 노드를 방문

    for i in sorted(edges[node]):
        if i not in visited_dfs:
            visited_dfs = dfs(i, visited_dfs)  # 재귀 호출 후 결과를 업데이트

    return visited_dfs  # 최종 결과를 리턴

이와 같이 local 변수를 사용할 때, visited_dfs는 모두 가지별로 동일하게 적용이 되어야 하므로, visited_dfs를 dfs를 호출하면서 수정해 주지 않았다.

 

 

- 스택

def dfs(node):
    stack=[node]
    visited = set()
    result = []
    while stack:
        value = stack.pop()
        if value in visited:
            continue
        result.append(value)
        visited.add(value)
        for neighbor in sorted(edges[value], reverse=True):  # graph[value]
            if not neighbor in visited:
                stack.append(neighbor)
    print(" ".join(map(str,result)))

처음에 스택으로 구현을 시도하였었지만 실패한 이유가 무엇일까.

 

이전에 짰던 코드와 비교해 보았다.

def dfs(start):
    visited = [False] * (n + 1)
    stack = [start]
    answer = []
    while stack:
        i = stack.pop()
        answer.append(i)
        visited[i] = True
        i_list = sorted(dict_n[i], reverse=True)
        for i_near in i_list:
            if not visited[i_near]:
                stack.append(i_near)
    return " ".join(map(str, answer))

if value in visited:

continue에 대한 부분이 없었다.

 

stack에 해당 idx를 넣을 때는 방문되지 않을 때일지 몰라도, 앞에 다른 stack 인자들이 pop되면서 특정 idx가 visited가 True가 될 수 있었기 때문이다.

 

이 부분을 놓쳐서 계속 실패했던 것 같다. 해당 부분을 수정해서 제출하니 통과가 되었다.

 

3. 코드 

DFS - 재귀 사용

from collections import deque


def dfs(node):
    visited_dfs.append(node)

    for i in sorted(edges[node]):
        if i not in visited_dfs:
            dfs(i)


def bfs(node):
    q = deque([node])
    visited_bfs.append(node)

    while q:
        node = q.popleft()
        for i in sorted(edges[node]):
            if i not in visited_bfs:
                visited_bfs.append(i)
                q.append(i)


if __name__ == "__main__":
    n, m, start = map(int, input().split())
    edges = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v = map(int, input().split())
        edges[u].append(v)
        edges[v].append(u)

    # DFS
    visited_dfs = []
    dfs(start)
    print(" ".join(map(str, visited_dfs)))

    # BFS
    visited_bfs = []
    bfs(start)
    print(" ".join(map(str, visited_bfs)))

 

DFS - 스택 사용

from collections import deque


def dfs(node):
    stack=[node]
    visited = set()
    result = []
    while stack:
        value = stack.pop()
        if value in visited:
            continue
        result.append(value)
        visited.add(value)
        for neighbor in sorted(edges[value], reverse=True):  # graph[value]
            if not neighbor in visited:
                stack.append(neighbor)
    print(" ".join(map(str,result)))


def bfs(node):
    q = deque([node])
    visited_bfs.append(node)

    while q:
        node = q.popleft()
        for i in sorted(edges[node]):
            if i not in visited_bfs:
                visited_bfs.append(i)
                q.append(i)


if __name__ == "__main__":
    n, m, start = map(int, input().split())
    edges = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v = map(int, input().split())
        edges[u].append(v)
        edges[v].append(u)

    # DFS
    visited_dfs = []
    dfs(start)

    # BFS
    visited_bfs = []
    bfs(start)
    print(" ".join(map(str, visited_bfs)))