Python3
문제
https://www.acmicpc.net/problem/1260
키워드
- 그래프
문제 풀이
문제 요구사항
- DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램
- 방문할 수 있는 정점이 여러 개일 때는 정점 번호가 작은 것을 먼저 방문한다
- 더이상 방문할 수 있는 점이 없는 경우 종료한다
- 정점 번호는 1번부터 N번까지이다.
- 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.
- 입력으로 주어지는 간선은 양방향이다.
변수 및 함수 설명
- n: 정점의 개수 (1 ≤ N ≤ 1,000)
- m: 간선의 개수 (1 ≤ M ≤ 10,000)
- v: 탐색을 시작할 정점의 번호
- adjList : 노드 간 연결 여부를 알려주는 2차원 배열
- visited : 방문했는지 확인하는 배열 (bool타입)
- bfsQueue : bfs에서 사용할 큐
- f : from. 화살표 쏜 노드
- t : to. 화살표 맞은 노드
- currentNumber : 큐의 제일 첫 번째 원소
- dfs(num) : dfs(깊이 우선 탐색)를 구현하는 함수
- bfs() : bfs(너비 우선 탐색)를 구현하는 함수
- clearVisited() : visited 배열을 초기화하는 함수
풀이
- 인접리스트 문제 adjList
- DFS는 재귀, BFS는 Queue로 푼다.
- visited는 방문했음을 알리는 배열로 타입은 bool이다.
BFS
- deque 사용하기
- 양방향 그래프이므로, 2차원 배열 adjList에 시작 노드와 끝 노드 두 번 담기
- bfsQueue에 탐색을 시작하는 정점의 번호 v를 담고, visited[v]는 True로 바꿔서 방문했음을 알리기
- bfs 함수 호출하기
(BFS 함수) - 23.5.7 풀이
- bfsQueue가 빌 때까지 반복한다
- currentNumber에 bfsQueue 첫 번째 원소 빼서 넣기 (놓친 부분: currentNumber를 해야 하는 건 생각이 났는데 어떤 값을 넣어야 하는지 생각이 나지 않았음. while문 위에서 선언했음. 위치 조심)
- adjList에서 currentNumber가 가리키는 노드만큼 반복한다. (놓친 부분: 어디를 반복해야 하는지 헷갈렸음)
- 만약 visited[element]가 True라면, 즉 이미 방문한 곳이면 continue
- 그렇지 않으면 visited[element]를 True로 바꾸고, 큐에 해당 값을 넣는다.
- 출력을 뭘 할까나! while문 안에 큐에 있는 원소를 뺀 값을 currentNumber 변수 안에 넣었다. 이 currentNumber 값을 출력하면 된다.
DFS
- 재귀 사용하기
- DFS는 재귀함수를 사용해야 하기 때문에 BFS와 달리 매개변수가 무조건 있어야 한다. (까먹지말기!)
(DFS 함수)
- adjList[num]이 가리키는 노드만큼 반복하기
- 만약 이미 방문한 노드면 continue
- 그렇지 않으면 visited[num]을 True로 바꾸고, dfs(num) 호출하기
- 출력은 들어오는 매개변수 num을 하면 된다.
(최종 출력)
- 문제 조건 중 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문"이 있기 때문에 정렬해야 한다.
- n+1만큼 반복하면서 adjList를 정렬한다.
최종 코드
from collections import deque
n, m, v = map(int, input().split())
adjList = [[] for _ in range(n+1)]
bfsQueue = deque([])
# visited 2차원 배열 - bool
visited = [False for _ in range(n+1)]
for i in range(m):
f, t = map(int, input().split())
adjList[f].append(t)
adjList[t].append(f)
# dfs - Recursion
def dfs(num) :
print(num, end = ' ')
for element in adjList[num] :
if visited[element] :
continue
visited[element] = True
dfs(element)
# bfs - Queue
def bfs() :
while bfsQueue :
currentNumber = bfsQueue.popleft()
print(currentNumber, end=' ')
for element in adjList[currentNumber] :
if visited[element] :
continue
visited[element] = True
bfsQueue.append(element)
def clearVisited() :
global visited
visited = [False for _ in range(n+1)]
# sort
for i in range(n+1):
adjList[i].sort()
# dfs - 방문 처리랑 인자 담은 dfs 호출
visited[v] = True
dfs(v)
print()
# visited 배열 초기화
clearVisited()
# bfs - 방문 처리랑 큐에 출발 노드 넣기
visited[v] = True
bfsQueue.append(v)
bfs()
I mean