.png&blockId=18f00b21-a9bc-4e35-aeb8-ecb07bddb89a)
DFS/BFS
DFS?
dfs란 무엇일까? depth first search? 그래프를 탐색할 때 깊은 곳을 우선탐색하고 다른노드로 넘어가 또 깊은곳을 탐색하는 스택 자료구조이다. 사용할 때 재귀함수를 활용한다.
만약 인접한 노드가 여러개일 경우 어떤 노드를 먼저 방문할지에 대한 고민이 필요하다. 더이상 방문하지 않은 노드가 없을 때 까지 반복하며, 재귀함수를 활용하기에 탈출조건을 항상 먼저 고려해야한다.
BFS?
bfs란 무엇일까? breadth frist search? 그래프를 탐색할 때, 인접한 노드를 우선탐색하며, 큐 자료구조를 사용한다. 파이썬은 큐 자료구조를 사용하기 위해 항상 collection라이브러리로부터 deque를 가져온다.
bfs역시 더이상 방문하지 않은 노드가 있을때까지 탐색을 해야한다.
1. 네트워크
고려해야할점
1.
방문처리를 위한 visited를 만들어야 한다.
2.
bfs 안의 파라미터들을 고려한다
접근방법
1.
방문하지 않은 컴퓨터를 만날 때 마다 bfs 실행한다.
2.
방문했을 때 다른 곳과의 연결이 끊어져 있다면 네트워크 1증가한다.
3.
방문헀던 곳은 True로 놓는다.
from collections import deque
def bfs(n, computers, node, visited):
if visited[node]==True:
return False
queue = deque([computers[node]])
visited[node] = True
while queue:
check = queue.popleft()
# 네트워크 연결이 되어 있는지 체크
for i in range(n):
# 자기자신 아니고, 연결(1)되어 있어야하고, 방문한적 없고
if i!=node and check[i]==1 and visited[i] == False:
visited[i] = True
queue.append(computers[i])
return True
def solution(n, computers):
global visited
visited = [False] * n
network = 0
for node in range(n):
if bfs(n, computers, node, visited):
network += 1
return network
Python
복사
막혔던 부분
자기자신이 아닌것을 고려했어야했는데, 한동안 왜 안되는지 이상한것만 건드렸었다.. 
2. 타겟 넘버
고려해야할 점
1.
dfs 파라미터를 고려한다.
2.
answer을 전역변수로 하는 global함수를 이해하고 있어야 한다.
3.
재귀함수는 탈출조건을 미리 고려해야 한다. (무한루프 방지)
4.
파이썬은 기본적으로 1000개까지의 재귀를 허용하도록 설정해 두었다.
다음과 같이 제한을 풀 수 있다
import
sys
limit_number = 10000
sys.setrecursionlimit(limit_number)
접근방법
1.
dfs 파라미터를 고려한다.
a.
idx, max_idx, result, numbers, target —> idx, result, numbers, target
2.
탈출조건을 고려한다.
a.
배열 안의 모든 수를 사용하였을 경우 return한다.
3.
target과 일치하는 값의 개수를 구하는 방법을 생각한다.
4.
dfs 내에서 더하는 로직보다는 파라미터를 활용해서 dfs를 사용하면 코드가 간결해진다.
a.
재귀로 함수를 실행할 때마다, index를 1 증가 시키고 result에 값을 더하거나 뺀다.
answer = 0
def solution(numbers, target):
global answer
dfs(0, 0, numbers, target)
return answer
# 인덱스, 최대길이, 결과값, 타겟, 배열
def dfs(idx, result, numbers, target):
global answer
if idx == len(numbers):
if result == target:
answer += 1
return
dfs(idx+1, result+numbers[idx], numbers, target)
dfs(idx+1, result-numbers[idx], numbers, target)
Python
복사
