문제
https://www.acmicpc.net/problem/1260
주요 아이디어
기본적인 DFS, BFS 구현 문제
- 따로 저장하지 말고 방문할 때마다 방문 처리로 출력을 진행해주자
- 문제에 명시되어 있진 않으나 예시를 보고 노드가 오름차순 정렬임을 유추할 수 있음
코드 구현 (Python 3)
더보기
def dfs(graph, v, visited):
visited.append(v)
print(v, end=' ')
# 인접 노드 방문
for adj in graph[v]:
if adj not in visited:
dfs(graph, adj, visited)
return None
from collections import deque
def bfs(graph, v):
queue = deque()
visited = [] # 방문처리
queue.append(v)
visited.append(v)
while queue:
now = queue.popleft()
print(now, end=' ')
# 인접노드 방문
for adj in graph[now]:
if adj not in visited:
queue.append(adj)
visited.append(adj)
return None
## test
n, m, v = map(int, input().split())
# 그래프 먼저 인접 리스트 형태로 구축하기
graph = [[] for _ in range(n+1)]
# 양방향 간선 입력 받기 -> sort 필요함
for _ in range(m):
s, e = map(int, input().split())
graph[s].append(e)
graph[e].append(s)
for i in range(1, n+1):
graph[i].sort()
dfs(graph.copy(), v, [])
print('')
bfs(graph.copy(), v)
제출 결과
코드 개선 방안
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 14501. 퇴사 (1) | 2024.04.06 |
---|---|
[BOJ] 14502. 연구소 (0) | 2024.04.06 |
[BOJ] 10866. 덱 (0) | 2022.09.07 |
[BOJ] 10845. 큐 (0) | 2022.09.07 |
[BOJ] 10828. 스택 (0) | 2022.09.07 |