[백준/Python] 1260. DFS와BFS & 1927. 최소 힙

 

1. 백준 1260. DFS와 BFS

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

1260번: DFS와 BFS

문제

  그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

  첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

  첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

from collections import deque

def dfs(x):
    visited[x] = 1
    result_dfs.append(x)

    for n in nums[x]:
        if visited[n] == 0:
            dfs(n)
    
    return result_dfs

def bfs(start):
    queue.append(start)

    while queue:
        # print(queue)
        # print(visited)
        temp = queue.popleft()
        visited[temp] = 1
        result_bfs.append(temp)
        for n in nums[temp]:
            if (visited[n] == 0) and (n not in queue):
                queue.append(n)
    
    return result_bfs


queue = deque()
result_dfs = []
result_bfs = []

n, m, start = map(int, input().split())
nums = [[] for _ in range(n+1)]
visited = [0 for _ in range(n + 1)]

for _ in range(m):
    x, y = map(int, input().split())
    nums[x].append(y)
    nums[x] = list(set(nums[x]))
    nums[x].sort()
    nums[y].append(x)
    nums[y] = list(set(nums[y]))
    nums[y].sort()

ans_dfs = dfs(start)
visited = [0 for _ in range(n + 1)]
ans_bfs = bfs(start)

print(' '.join(map(str, ans_dfs)))
print(' '.join(map(str, ans_bfs)))

• dfs 코드와 bfs 코드를 모두 구현해서 뿌듯했다.
• 다만 입력받는 노드와 간선을 처리하는 과정에서 시간이 많이 소요됐다.
• 양방향 간선이기 때문에 nums[x] = y 와 nums[y] = x 두 처리 모두가 필요했으며, set을 이용해서 중복으로 겹치지 않게 했다.
• 작은 수 부터 방문하기 위해 sort를 통해 정렬했다.

---

 

2. 백준 1927. 최소 힙

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

1927번: 최소 힙

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

  첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

출력

  입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

from heapq import heappop, heappush
import sys

n = int(sys.stdin.readline())
heap = []

for _ in range(n):
    temp = int(sys.stdin.readline())
    
    if temp == 0:
        if len(heap) == 0:
            print(0)
        else: print(heappop(heap))
    else:
        heappush(heap, temp)

• heapq 자료구조를 이해하고 heappop, heappush를 적절히 사용할 수 있어야 했다.
• 문제 풀이의 핵심은 input이었다. sys.stdin.readline()으로 바꾸지 않으니 시간초과가 났고 변경 후 풀이를 완료할 수 있었다.