[프로그래머스] 고득점Kit (8) - DFS/BFS (파이썬)

1. 타겟 넘버 (Lv. 2)

# 타겟 넘버
def solution(numbers, target):
    answer = 0

    def dfs(target, k, result):
        nonlocal answer
        if k == len(numbers):
            if target == result:
                answer += 1
            return
        else:
            dfs(target, k+1, result+numbers[k])
            dfs(target, k+1, result-numbers[k])

    dfs(target, 0, 0)
    return answer

 

재귀 함수를 이용한 dfs로 풀었다.

k == len(numbers) 일 경우, target과 같은지 확인

return answer

---

2. 네트워크 (Lv. 3)

# 네트워크
from collections import deque


def solution(n, computers):
    parent = [i for i in range(n)]
    for i in range(n):
        bfs(i, parent, computers)
    parent = set(parent)
    return len(parent)


def bfs(start, parent, computers):
    q = deque()
    q.append(start)
    while q:
        node = q.popleft()
        for nnode in range(len(computers[node])):
            if node != nnode and computers[node][nnode] == 1:
                if parent[nnode] != parent[node]:
                    parent[nnode] = parent[node]
                    q.append(nnode)

 

parent리스트를 자기 자신으로 초기화

bfs를 이용해서 부모가 다를 경우 부모 값을 이전 값을 초기화를 해준다.

parent를 set()로 변환 : 중복 값 전부 제거

return len(parent) : 집합의 개수 출력

---

3. 단어 변환 (Lv. 3)

# 단어 변환
from collections import deque


def solution(begin, target, words):
    if target not in words:
        return 0
    answer = bfs(begin, target, words)
    return answer


def bfs(begin, target, words):
    visited = [False] * len(words)
    q = deque()
    q.append((begin, 0))
    while q:
        word, cnt = q.popleft()
        if word == target:
            return cnt
        for i in range(len(words)):
            if visited[i] == True:
                continue
            diff = 0
            for x, y in zip(word, words[i]):
                if x != y:
                    diff += 1
            if diff == 1:
                q.append((words[i], cnt + 1))
    return 0

 

bfs를 이용하면서 현재 단어와 하나만 차이(diff == 1)나는 단어들을 q에 append

visited를 체크해주면서 이전 단어는 방문하지 않돌록 관리

---

4. 여행 경로 (Lv. 3)

# 여행 경로
def solution(tickets):
    arr = {}
    for start, end in tickets:
        if not arr.get(start):
            arr[start] = [end]
        else:
            arr[start].append(end)
    for temp in arr:
        arr[temp].sort(reverse=True)
    answer = dfs(arr)
    return answer


def dfs(arr):
    stack = ['ICN']
    path = []
    while len(stack) > 0:
        top = stack[-1]
        if top not in arr or not arr[top]:
            path.append(stack.pop())
        else:
            stack.append(arr[top].pop())
    path.reverse()
    return path

 

while문을 이용한 dfs로 풀었다.

경로를 딕셔너리화해서 arr에 넣어주고, 역순으로 정렬

stack의 시작은 ['ICN']

stack의 키값이 딕셔너리에 없거나 딕셔너리[키]에 값이 없다면 path리스트에 stack.pop을 추가해준다.

그 외에는, 딕셔널리에서 pop을 해와서 stack에 추가

path는 뒤에서부터 입력이 됐으므로, reverse이후 return