[파이썬 코테 대비 동아리]개념을 공부하자_BFS,DFS편

BFS? DFS?

: BFS : Breadth-First Search, 너비 우선 탐색

DFS : Depth-Fisrt Search, 깊이 우선 탐색

그래프를 탐색하는데 쓴다. 그래프는 노드(node)와 엣지(edge)로 이루어진 자료구조의 일종인데, 트리와는 차이가 있다.

1. 방향성 = 그래프는 방향과 무방향 모두 가능하지만, 트리는 방향 그래프만 존재한다
2. 사이클 = 그래프는 순환, 사이클, 비순환 모두 존재하지만, 트리는 모두 불가능에 비순환만 존재한다.
3. 부모 자식 = 그래프는 부모-자식 개념x 트리는 있다. 순서 존재

예를 들어 그래프는 지도, 지하철 노선도 정도고, 트리는 이진 트리 , 이진 탐색 트리 정도?로 보면 된다. 진짜 간단하게 말하면 그래프 중에서 방향성있는 비순환 그래프가 트리이다.

DFS - 깊이 우선 탐색

: 최대한 깊이 내려간 뒤 더 이상 갈 수 없는 경우 옆으로 이동

출처 https://developer-mac.tistory.com/64

쉬운 예로, 미로 찾기가 있다. 쭉 가다가 더 이상 못 가면 가장 가까운 갈림길로 가서 다른 방향으로 가는 걸 생각하면 된다.

DFS의 경우

1. 모든 노드 방문하고자 할 경우
2. DFS가 BFS보다 좀 더 간단하다
3. 속도는 BFS보단 느리다

의 특징을 가지고 있다.

BFS - 너비 우선 탐색

: 최대한 옆으로 간 뒤 더 갈 수 없다면 아래로 이동

출처 https://developer-mac.tistory.com/64

쉬운 예로 배민 시킬 때 치킨을 먹을거다 ! 하면 전체탭에선 관심없는 메뉴의 가게까지 모두 봐야하지만 치킨 탭으로 가면 치킨만 모아서 원하는 가게 선택 가능하다… 라고 보면 됨

DFS vs BFS

: DFS는 스택 또는 재귀로 표현하고, BFS는 큐를 이용하면 좋다.

시간복잡도는 동일하다.

1. 그래프의 모든 노드를 방문해야하는 문제
2. DFS BFS 중 편한 것 선택
3. 경로의 특징 저장
4. DFS사용이 편함
5. 최단거리
6. BFS유리
7. 검색 대상의 범위
8. 크다면 BFS, 작다면 DFS

예시 문제들을 풀어보좌좟

1.https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3

[타겟넘버]

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

• 1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4 +4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

<코드와 알고리즘>

일단…문제 보니 DFS써야 할 것 같다. 모든 경우의 수를 확인해야 하므로!

DFS는 스택 또는 재귀를 쓰면 되므로 스택을 써보겠다.라고 생각은 해봤지만 구글링없이는 도저히.. 못풀겠어서 BFS로 도망쳐 본다.

BFS에서는 첫 numbers[0]의 값에다 *1과 *(-1)을 한 거 + 똑같은 방법으로 numbers[1]의 값들을 더해준 걸 또 내려가는…식으로 …..도 뭔가 답이 없음 ㅠㅠㅠㅠㅠㅠ어쩔 수 없이 구글링한!! depth로 해야겠다…..

재귀를 함께 사용해주는데, 심도가 5가 되면 그 값을 반환하는 코드이다

def solution(numbers, target):
	answer = DFS(numbers, target, 0)
	return answer

def dfs(numbers,target,depth):
	answer = 0
	if depth == len(numbers):
		print(numbers)
		if sum(numbers) == target:
		return 1
		else: return 0
	else:
		answer += dfs(numbers,target,depth+1)
		numbers[depth] *=-1		
		answer += dfs(numbers,target,depth+1)
		return answer

2.https://www.acmicpc.net/problem/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

예제 입력 3

1000 1 1000
999 1000

예제 출력 3

BFS? DFS?

: BFS : Breadth-First Search, 너비 우선 탐색

DFS : Depth-Fisrt Search, 깊이 우선 탐색

그래프를 탐색하는데 쓴다. 그래프는 노드(node)와 엣지(edge)로 이루어진 자료구조의 일종인데, 트리와는 차이가 있다.

1. 방향성 = 그래프는 방향과 무방향 모두 가능하지만, 트리는 방향 그래프만 존재한다
2. 사이클 = 그래프는 순환, 사이클, 비순환 모두 존재하지만, 트리는 모두 불가능에 비순환만 존재한다.
3. 부모 자식 = 그래프는 부모-자식 개념x 트리는 있다. 순서 존재

예를 들어 그래프는 지도, 지하철 노선도 정도고, 트리는 이진 트리 , 이진 탐색 트리 정도?로 보면 된다. 진짜 간단하게 말하면 그래프 중에서 방향성있는 비순환 그래프가 트리이다.

DFS - 깊이 우선 탐색

: 최대한 깊이 내려간 뒤 더 이상 갈 수 없는 경우 옆으로 이동

출처 https://developer-mac.tistory.com/64

쉬운 예로, 미로 찾기가 있다. 쭉 가다가 더 이상 못 가면 가장 가까운 갈림길로 가서 다른 방향으로 가는 걸 생각하면 된다.

DFS의 경우

1. 모든 노드 방문하고자 할 경우
2. DFS가 BFS보다 좀 더 간단하다
3. 속도는 BFS보단 느리다

의 특징을 가지고 있다.

BFS - 너비 우선 탐색

: 최대한 옆으로 간 뒤 더 갈 수 없다면 아래로 이동

출처 https://developer-mac.tistory.com/64

쉬운 예로 배민 시킬 때 치킨을 먹을거다 ! 하면 전체탭에선 관심없는 메뉴의 가게까지 모두 봐야하지만 치킨 탭으로 가면 치킨만 모아서 원하는 가게 선택 가능하다… 라고 보면 됨

DFS vs BFS

: DFS는 스택 또는 재귀로 표현하고, BFS는 큐를 이용하면 좋다.

시간복잡도는 동일하다.

1. 그래프의 모든 노드를 방문해야하는 문제
2. DFS BFS 중 편한 것 선택
3. 경로의 특징 저장
4. DFS사용이 편함
5. 최단거리
6. BFS유리
7. 검색 대상의 범위
8. 크다면 BFS, 작다면 DFS

예시 문제들을 풀어보좌좟

1.https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3

[타겟넘버]

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

• 1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4 +4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

<코드와 알고리즘>

일단…문제 보니 DFS써야 할 것 같다. 모든 경우의 수를 확인해야 하므로!

DFS는 스택 또는 재귀를 쓰면 되므로 스택을 써보겠다.라고 생각은 해봤지만 구글링없이는 도저히.. 못풀겠어서 BFS로 도망쳐 본다.

BFS에서는 첫 numbers[0]의 값에다 *1과 *(-1)을 한 거 + 똑같은 방법으로 numbers[1]의 값들을 더해준 걸 또 내려가는…식으로 …..도 뭔가 답이 없음 ㅠㅠㅠㅠㅠㅠ어쩔 수 없이 구글링한!! depth로 해야겠다…..

재귀를 함께 사용해주는데, 심도가 5가 되면 그 값을 반환하는 코드이다

def solution(numbers, target):
	answer = DFS(numbers, target, 0)
	return answer

def dfs(numbers,target,depth):
	answer = 0
	if depth == len(numbers):
		print(numbers)
		if sum(numbers) == target:
		return 1
		else: return 0
	else:
		answer += dfs(numbers,target,depth+1)
		numbers[depth] *=-1		
		answer += dfs(numbers,target,depth+1)
		return answer

2.https://www.acmicpc.net/problem/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

예제 입력 3

1000 1 1000
999 1000

예제 출력 3