1.문제 링크
https://www.acmicpc.net/problem/1260
2. 풀이 전 계획과 생각
- DFS와 BFS에 대한 정확한 이해(목적/필요성)
- stack / queue 등 자료구조 및 기본적인 메소드에 대한 이해
- N(정점의 수)/ M(간선의 수)/ V(루트노드) 입력부터 시작하여 DFS/BFS 구현까지!
- 먼저 이해하고 그 이후에 응용하는 것이 필요!
3. 풀이
- DFS/BFS의 목적과 필요성
자료를 모두 탐색한다는 점에서는 유사하지만,
이를 탐색하기 위한 도구인자료구조를 각각 다른 방법으로 활용한다는 점이 중요 포인트! - DFS
하나의 경우의 수에 대한 가능한 모든 경우의 수를 끝까지 탐색한다.
#깊이우선탐색#stack#Last In First Out - BFS
여러가지 경우의 수에 대한 가능한 단계별 경우의 수를 탐색한다.
#넓이우선탐색#queue#First In First Out
# DFS
# Depth first search
# 깊이우선탐색, 루트노드를 시작으로 깊이우선탐색하여 노드들을 조회하는 방법
# Input : 정점의 개수 - 간선의 개수 - 시작노드
# 1 2
# 1 3
# 1 4
# 2 4
# 3 4
# 깊이탐색은 깊이우선, 1 2 4 3
# 숫자를 입력받았을때 이를 그래프로 구현하는 로직
# 먼저 그래프부터 만들기
graph = {
1: [2, 3, 4],
2: [1, 4],
3: [1, 4],
4: [1, 2, 3]
}
# DFS
# 완전이진트리가 아닌 정점이나 인접노드가 여러개인 그래프 등
# 모두 적용가능한 코드필요
# stack 이용
# pop, extend
def dfs(graph, root_node):
#시작노드
stack = [root_node]
result = []
while stack:
#이후 반복문을 돌리기 위한 요소 : 부모노드
parent_node = stack.pop()
#방문한 시점에서 결과리스트에 추가
#자식노드는 stack에 추가
if parent_node not in result:
result.append(parent_node)
children = graph[parent_node]
#탐색은 낮은 숫자부터 진행하기위해
#리스트의 마지막 숫자가 가장 작아야 한다(내림차순)
#stack에 추가하기전에 자식노드 재배열
children.reverse()
#재배열후 stack에 추가
stack.extend(children)
return result
# BFS
# 완전이진트리가 아닌 정점이나 인접노드가 여러개인 그래프 등
# 모두 적용가능한 코드필요
# Queue 이용
# dequeue, extend
# dequeue = pop(0)
def bfs(graph, root_node):
#시작노드
queue = [root_node]
result = []
while queue:
#이후 반복문을 돌리기 위한 요소 : 부모노드
#bfs는 queue에서 pop
parent_node = queue.pop(0)
#방문한 시점에서 결과리스트에 추가
#자식노드는 stack에 추가
if parent_node not in result:
result.append(parent_node)
children = graph[parent_node]
# 탐색은 낮은 숫자부터 진행하기위해
# 리스트의 첫번째 숫자가 가장 작아야 한다(오름차순)
# stack에 추가하기전에 자식노드 재배열
children.sort()
#재배열후 queue에 추가
queue.extend(children)
return result
print(dfs(graph, 1))
print(bfs(graph, 1))
3-1. 풀이하면서 참조한 링크
https://jeinalog.tistory.com/18
4. 풀이하면서 고민했던 점
- 문제의 N/V/M을 매개변수로 하여 graph를 바로 구현할 수는 없을까?
정점의 개수, 간선의 개수, 루트 노드를 매개변수로 받고, 이를 그래프로 구현할 수 있는 로직이 있을지 더 생각해 보자. - 구현한 그래프의 자식노드(리스트)의 순서와 상관없이 탐색을 작은 숫자부터 하도록 구현!
루트노드를 stack/queue에 넣은 이후에, 자식노드에 대한 선언을 별도로 하고 이를 재배열하여 정방향으로 탐색이 되도록 유도해보자. - 알고리즘을 구현하는데 너무 시간이 오래걸린다
다른 방향으로 생각하는 것도 중요하지만, 시간을 절약하는 것도 매우 중요하다.
10분내외로 생각하고 알고리즘 구현하는 것까지 가능하도록 꾸준히 연습해보자. - 클린코드
가독성이 좋은 코드, 이해가 쉬운 코드의 조건들을 생각해보자.
5. 문제를 풀고 알게된 개념 및 소감
DFS/BFS
깊이우선탐색 / 넓이우선탐색stack/queue
LIFO-깊이우선탐색 / FIFO-넓이우선탐색dictionary(hash table)
dict = { key: [value[0], value[1],...] }
트리 및 그래프를 구현하는데 dictionary를 이용array.sort() / array.reverse()
배열의 원소들을 정렬해주는 메소드
sort() - 오름차순 / reverse() - 내림차순list.append(node)
배열/리스트에 노드(원소) 단위로 추가할때 사용하는 메소드list.extend(list)
배열/리스트에 배열/리스트 단위로 추가할때 사용하는 메소드
여러 노드를 추가할때 사용함
5-1. remind
코드에 대한 이해가 우선이다. sugar syntax보다는 sugar logic!
