[DFS] 개념이해 및 Programmers lv.2 타겟넘버 (자료구조)

개념 이해

자료구조란?

[Data Structures] 자료구조란?

 

자료구조 트리선회

[Data Structures] 트리선회 (DFS & BFS)

- DFS 알고리즘은 트리로 이해하는 것이 가장 쉬움

- 트리에서 Depth를 내려갔다가 다시 올라가고 for문과 섞여 있어서 이해하기 쉬움

- 재귀함수 호출을 depth(깊이로) 경우의 수를 Breadth(너비)로 생각해보아라.

- depth 는 트리의 깊이

 

문제

10 이하의 자연수 N을 입력받아 주사위 N번 던져서 나올 수 있는 모든 경우를 출력하는 프로그램을 작성하시오.

-> 10이하의 자연수 중에 하나 선택한다. 3이다 그럼 주사위를 3번 던져 그리고 나올 수 있는 주사위 눈금의 집합의 모든 경우의 수를 구하라는 말

 

입력 예: 3

출력 예:

 

1 1 1 

1 1 2

1 1 3

1 1 4

1 1 5

1 1 6

1 2 1

1 2 2

1 2 3

.

.

.

6 6 6 

 

N이 2이면 2중 for  -> Depth

N이 3이면 3중 for

N이 4이면 4중 for

등

등

 

ex) N이 1이면 Depth가

1 2 3 4 5 6 

 

N이 2면 Depth가 2 그래서 깊이를 두번탐

1    1    1           1

1    2   3 . . . . . 6           

 ---------------

2 2        2

1 2 . . . . 6

 

Depth는 재귀함수를 Call하는 부분은 depth가 됨 깊이!!

옆으로 긴 Breadth는 늘어나는 숫자가 되는 것이다. 

 

만약에 삼성전자 위아래왼쪽오른쪽이라고 하면

아래의 노드의 1 2 3 4 5 6 처럼 위 아래 왼쪽 오른쪽이 옆으로 펼쳐진 것이다.

그리고 

 

Depth 로 내려가는건 DFS를 Call 하는거고

옆으로 가는건 for문에서 해준다

ex) 만약에 방향들을 늘어놓을 떄는 - - --  - - -

정해지지 않은건 depth를 이용해서 if를 이용해서 빠져나간다.

 

 

 

바이러스 문제

 

입력

첫째줄 - 컴퓨터의 수가 주어짐. 컴퓨터의 수는 100개 이하, 각 컴퓨터는 1부터 차례대로 번호가 매겨진다.

둘때줄 - 네트워크 상에서 직접 연결되어 있는 컴퓨터의 쌍의 수가 주어진다. 

이어서 그 수만큼 한줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 번호가 주어진다.

 

7 - 노드의 수

6 - 간선의 수

연결된 노드의 쌍

1 2

2 3

1 5

5 2

5 6

4 7 

 

 

출력

1번 컴퓨터가 웜바이러스에 걸렸을때 1번 컴퓨터를 통해 웜바이러스에 걸리게되는 컴퓨터의 수를 첫째줄에 출력한다.

 

 

노드 개수만큼 벌어지는거 그것이 n

재귀함수니까 조건주고 빠져나가면 됨

 

참고 출처

www.youtube.com/watch?v=RNU2j-l6mCM

 

DFS는

1. 스택 자료구조(혹은 재귀함수)이용하며  

2. 깊은 부분 우선탐색

 

.1. 탐색 시작 노드를 스택에 삽입하고 방문처리

2. 스택의 최상단 노드에 방문하지않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 합니다. 빙문하지 않으 ㄴ인접노드가 없으면 스택에서 최상단  노드를 꺼냅니다.

3. 더이상 2번의 과정을 수행할 수 없을때까지 반복한다.

 

번호/ 노드의 정보

노드간 연결된 정보

연결됐다! 연결됐다는걸 어떻게 코드로 구현함?

방문했다는건 어떻게 구현?

재귀는 어떤식으로 이루어지는가?

 

1번 노드는 2 3 8

2번 노드는 1 7 과 연결

3번노드는 1 4 5 노트와 연결 . 을 표현함

 

시작노드 방문처리

방문처리한 노드를 출력하고

그 노드와 연결된 노드를 확인하면서

 

가작 마지막에 불러온 함수가 가장먼저 출력됨

그래서 스택대신 재귀함수로 하는게 일반적

 

그 인접하 노드를 방문하지 않았다면ㄱ ㅒ를 다시 DFS호출

인접한 노드 표현! ! !

 

 

www.youtube.com/watch?v=PqzyFDUnbrY