0. 문제
'''
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,
더 이상 방문할 수 있는 점이 없는 경우 종료한다.
정점 번호는 1번부터 N번까지이다.
# 입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다.
다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
# 출력
첫째 줄에 DFS를 수행한 결과를,
그 다음 줄에는 BFS를 수행한 결과를 출력한다.
V부터 방문된 점을 순서대로 출력하면 된다.
'''
'''
예제 1
4 5 1
1 2
1 3
1 4
2 4
3 4
1 2 4 3
1 2 3 4
'''
'''
예제 2
5 5 3
5 4
5 2
1 2
3 4
3 1
3 1 2 5 4
3 1 4 2 5
'''
'''
예제 3
1000 1 1000
999 1000
1000 999
1000 999
'''
1. 첫번째 답
from collections import deque
# 정점의 개수, 간선의 개수, 시작 정점 입력받기
n, m, v = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(m)]
# 그래프 생성
graph = {i: [] for i in range(1, n + 1)} # 1부터 n까지의 정점 초기화
for i, j in arr:
graph[i].append(j)
graph[j].append(i)
# 그래프 오름차순 정렬
for key in graph:
graph[key].sort()
def DFS(v):
visited_dfs.append(v) # 현재 정점 방문 처리
# 현재 정점과 연결된 정점 정렬 후 방문
for node in graph[v]:
if node not in visited_dfs:
DFS(node)
def BFS(v):
queue = deque()
queue.append(v)
visited_bfs.append(v) # 현재 정점 방문 처리
# queue 가 다 빌 때까지 그래프 방문
while queue:
q = queue.popleft() # 최하단 노드 뽑기
for node in graph[q]:
if node not in visited_bfs:
visited_bfs.append(node) # 방문처리
queue.append(node) # 큐에 미방문 노드 넣기
# 방문할 정점을 기록할 리스트
visited_dfs = []
DFS(v)
print(*visited_dfs)
visited_bfs = []
BFS(v)
print(*visited_bfs)
1. 입력받은 그래프를 딕셔너리로 재구성함
1 2
1 3
-> {1: [2, 3], 2: [1], 3: [1]}
처음에는 입력받은 내용 자체로 진행하려고 했는데 코드 진행이 잘 안풀렸음.
그래서 노드 별 연결된 인접 노드를 딕셔너리로 묶기로 함. (키 값으로 호출하기 위해서)
정점이 1000개인데 연결 노드가 1 라면 딕셔너리에 {999: [1000], 1000: [999]} 이렇게만 넣고 싶었는데
이렇게 if 문을 매 노드마다 거니까 런타임 에러가 나는거임..
그래서 그냥 딕셔너리를 정점 개수만큼 만들고 간선이 있는 노드에만 값을 append 해줌.
나는 이렇게 하면 메모리 낭비가 많이 일어날 거라고 생각했는데,
뤼튼 왈, 수만개까지 해도 충분히 처리할 수 있다고 함..
맞히긴 했는데 시간이 .. 무엇?
코드 리팩토링이 필요해보임.
2. 두번째 답
from sys import stdin as s
from collections import deque
# 정점의 개수, 간선의 개수, 시작 정점 입력받기
n, m, v = map(int, s.readline().split())
# 그래프 생성
graph = [[] for _ in range(n + 1)] # 1부터 n까지의 정점 초기화
for _ in range(1, m + 1):
a, b = map(int, s.readline().split())
graph[a].append(b)
graph[b].append(a)
# 그래프 오름차순 정렬
for nodes in graph:
nodes.sort()
def DFS(v):
visited_dfs.append(v) # 현재 정점 방문 처리
# 현재 정점과 연결된 정점 정렬 후 방문
for node in graph[v]:
if node not in visited_dfs:
DFS(node)
def BFS(v):
queue = deque()
queue.append(v)
visited_bfs.append(v) # 현재 정점 방문 처리
# queue 가 다 빌 때까지 그래프 방문
while queue:
q = queue.popleft() # 최하단 노드 뽑기
for node in graph[q]:
if node not in visited_bfs:
visited_bfs.append(node) # 방문처리
queue.append(node) # 큐에 미방문 노드 넣기
# 방문할 정점을 기록할 리스트
visited_dfs = []
DFS(v)
print(*visited_dfs)
visited_bfs = []
BFS(v)
print(*visited_bfs)
속도를 높일 수 있는 방법을 찾다가, sys 로 여러줄의 입력값을 빠르게 받는 방법을 찾음.
그리고 딕셔너리를 정점 개수만큼 만들거면 리스트와 별 차이가 없어서 리스트로 바꿔봄.
속도가 반으로 줄어듦!
근데 ; Pypy로 제출하니까 속도가 100ms 나 줄었는데 메모리가.. 거의 세배를 .. 씀..
찾아보니, Pypy 는 반복문에 최적화되어 있어서 (그것땜에 메모리 씀)
- 속도가 중요한 문제일 경우 Pypy
- 메모리가 제한적인 경우 Python3 로 제출하는게 좋다고 한다!
3. 세번째 답
왠지 속도와 메모리 사용량을 더 줄일 방법이 있을 것 같아서 GPT 한테 방법을 물어봄.
메모리 최적화
1. visited를 집합(set)으로 변경
- 리스트에서의 탐색 시간 O(n) → 집합에서 탐색 시간 O(1).
- 메모리 사용량도 줄어듦.
2. defaultdict를 사용한 그래프 저장
- 불필요한 리스트 초기화를 줄여 메모리를 절약.
3. 재귀 DFS를 스택 기반 반복으로 변환
- 재귀 호출로 인해 발생하는 추가 스택 사용을 제거.
속도 최적화
1. 입력 처리 개선
- stdin.read로 대량 입력을 빠르게 처리.
2. 정렬된 상태로 그래프 저장
- 탐색할 때마다 정렬하지 않도록, 초기 정렬 시 처리.
3. 방문 여부 체크 최적화
- 리스트 기반 체크 → 집합 기반 체크.
from sys import stdin
from collections import deque, defaultdict
# 입력 받기
n, m, v = map(int, stdin.readline().split())
# 그래프 생성
graph = defaultdict(list)
for _ in range(m):
a, b = map(int, stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
# 그래프 정렬 (정렬된 상태로 저장)
for key in graph:
graph[key].sort()
def DFS_iterative(v):
stack = [v]
visited = set()
result = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
result.append(node)
# 방문할 노드를 역순으로 추가 (그래야 작은 노드부터 탐색)
stack.extend(reversed(graph[node]))
return result
def BFS(v):
queue = deque([v])
visited = set([v])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
# DFS와 BFS 실행
print(*DFS_iterative(v))
print(*BFS(v))
와웅..
이번엔 파이썬이 훨씬 빨라..
어웅 근데 아직 이 코드가 잘.. 뭔가 이해가 안된다.. 아직. 능력치 부족!
