백준 1260번 DFS와 BFS
문제 설명
그래프를 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
1 2 4 3
1 2 3 4
예제 입력 2
5 5 3
5 4
5 2
1 2
3 4
3 1
예제 출력 2
3 1 2 5 4
3 1 4 2 5
그래프 이론
이 문제는 그래프 탐색을 사용하여 해결하는 문제입니다.
깊이 우선 탐색과 너비 우선 탐색의 개념을 공부하시고 구현해보신 다음에 푸는 것을 추천드립니다
기본적인 깊이 우선 탐색과 너비 우선 탐색의 코드에 몇 가지 조건을 추가로 넣어 주면서 풀었습니다.
2가지 문제 조건을 주의 깊게 봐야 하는데
방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
입력으로 주어지는 간선은 양방향
이 두 가지 때문에 저는 헤맸습니다.
입력받아 딕셔너리에 저장
graph_list = { }
node , edge , root = input().split()
node , edge , root = int(node), int(edge) , int(root)
for n in range(edge):
node1,node2 = input().split()
node1,node2 = int(node1),int(node2)
if node1 not in graph_list.keys():
graph_list[node1] = [node2]
else:
graph_list[node1].append(node2)
if node2 not in graph_list.keys():
graph_list[node2] = [node1]
else:
graph_list[node2].append(node1)
우선 입력 형식에 따라서 딕셔너리를 만듭니다.
for 문을 통해 입력받은 정점 두 개를 딕셔너리에 key 값과 value 값으로 저장합니다.
그래프 이론에서 key와 value 값을 사용하는 것은 간선이 노드에서 노드로 향하는 것을 의미하는데
이 문제는 양방향 간선이 입력으로 주어지기 때문에 저는 노드 1이 키가 되는 경우와 값이 되는 경우 모두 저장해 주었습니다.
입력이 아래와 같을 때 저장되는 형식은
4 5 1
1 2
1 3
1 4
2 4
3 4
graph_list = {1: [2, 3, 4], 2: [1, 4], 3: [1, 4], 4: [1, 2, 3]}
깊이 우선 탐색 DFS 함수
def dfs (graph,root):
visited =[]
stack = [root]
while stack:
print(stack)
now = stack.pop()
if now not in visited:
visited.append(now)
if now in graph.keys():
stack += sorted(list((set(graph[now]) - set(visited))),reverse=True)
stack을 사용한 깊이 우선 탐색에서 한 가지 조건을 추가해 줍니다.
방문할 수 있는 정점이 여러 개가 되는 경우가 있습니다.
그때 정점 번호가 작은 것을 먼저 방문하기 위해서
스택에 넣어주는 정점을 내림 차순으로 바꿔줍니다
스택에서 마지막으로 들어간 것이 먼저 pop 되기 때문입니다.
너비 우선 탐색 BFS 함수
def bfs (graph,root):
visited =[]
queue = deque([root])
while queue:
print(queue)
now = queue.popleft()
if now not in visited:
visited.append(now)
if now in graph.keys():
queue += sorted(list((set(graph[now])) - set(visited)))
return visited
queue를 사용한 너비 우선 탐색에서도
큐에 다음 정점들을 삽입할 때 정렬되어서 들어갈 수 있게 추가해줍니다.
큐는 먼저 들어간 것이 먼저 pop 되기 때문에 오름차순으로 정렬합니다.
전체 python 코드
from collections import deque
graph_list = { }
node , edge , root = input().split()
node , edge , root = int(node), int(edge) , int(root)
for n in range(edge):
node1,node2 = input().split()
node1,node2 = int(node1),int(node2)
if node1 not in graph_list.keys():
graph_list[node1] = [node2]
else:
graph_list[node1].append(node2)
if node2 not in graph_list.keys():
graph_list[node2] = [node1]
else:
graph_list[node2].append(node1)
def dfs (graph,root):
visited =[]
stack = [root]
while stack:
now = stack.pop()
if now not in visited:
visited.append(now)
if now in graph.keys():
stack += sorted(list((set(graph[now]) - set(visited))),reverse=True)
return visited
def bfs (graph,root):
visited =[]
queue = deque([root])
while queue:
now = queue.popleft()
if now not in visited:
visited.append(now)
if now in graph.keys():
queue += sorted(list((set(graph[now])) - set(visited)))
return visited
print(' '.join(str(x) for x in (dfs(graph_list,root))))
print(' '.join(str(x) for x in (bfs(graph_list,root))))
오늘의 삽질
정렬된 리스트를 set형식으로 만들면 정렬이 깨진다
sorted 함수 : 원본 값 그대로 정렬 값 반환 / sort 함수 : 원본 값 직접 수정
list로 집합
- 합집합 : list(set(A) | set(B))
- 교집합 : list(set(A) & set(B))
- 차집합 : list(set(A) - set(B))
자료형을 잘 보자-프로그래밍 중간중간 출력해보면서 결과를 확인하는 작업이 중요한 것 같다
그렇지 않으면 몇 줄 안 되는 코드에서 어디가 잘못된 것인지 한참 추적해야 하는데 시간이 오래 걸린다.
입력을 잘 처리하면 더 많은 조건을 달려고 길게 코딩할 필요 없이 문제를 빨리 해결할 수 있으니
입력받은 데이터를 어떻게 할지 고민하면서 문제를 풀자
내 코드 에디터에서 에서 입출력 잘된다고 발로 손뼉 치고 좋아하다가
백준 코딩에 제출하니 틀렸다고 해서 한참 헤맸다.
알고 보니 출력 형식이 리스트가 아니었다. 꼼꼼히 확인하자
코드가 쫌 지저분한 것 같다
파이썬을 파이썬답게 쓰는 방법을 알아봐야겠다.
2차원 행렬로 DFS/BFS 구현해보기
