programmers_고득점키트(DFS,BFS)

작성일 | In

깊이/너비 우선 탐색(DFS,BFS)

1. 타겟넘버

  • No Image

  • 반복문 이용

def solution(numbers, target):
    answer = [0]
    for i in numbers:
        temp = []
        for j in answer:
            temp.append(j+i)
            temp.append(j-i)
        answer = temp
    return answer.count(target)


print(solution([1, 1, 1, 1, 1], 3))
  • No Image
  • 재귀함수 이용
def solution(numbers, target):
    if not numbers and target == 0:
        return 1
    elif not numbers:
        return 0
    return solution(numbers[1:], target + numbers[0]) + solution(numbers[1:], target-numbers[0])

2. 네트워크

  • 문제를 이해하는 데에도 많은 시간이 걸렸던 문제.
  • DFS를 사용한, 완전 탐색 문제다.
def Network(computers, visited, StartNode):
    stack = [StartNode]  # 스택에 idx 하나 넣고 시작
    while stack:  # 스택이 빌 때가지
        path = stack.pop()  # 꺼내고
        if not visited[path]:  # 방문하지 않았다면
            visited[path] = True
        for i in range(len(computers)):
            if computers[path][i] == 1 and not visited[i]:
                stack.append(i)


def solution(n, computers):
    answer = 0
    visited = [False for _ in range(n)]  # 방문했음을 표시
    idx = 0
    while not all(visited):  # 모든 노드가 True가 될 때까지
        if not visited[idx]:
            Network(computers, visited, idx)
            answer += 1
        idx += 1
    return answer
  • No Image

3. 단어 변환

  • BFS를 이용해서 푸는 문제다.

  • No Image

  • 이 문제 역시 정말 어려웠다.

  • 단계별로 천천히 생각해야한다.

from collections import deque as queue


def transistable(a, b):
    return sum((1 if x != y else 0)for x, y in zip(a, b)) == 1


def solution(begin, target, words):
    q, d = queue(), dict()
    q.append((begin, 0))
    d[begin] = set(filter(lambda x: transistable(x, begin), words))
    for w in words:
        d[w] = set(filter(lambda x: transistable(x, w), words))

    while q:
        print(q)
        cur, level = q.popleft()
        if level > len(words):
            return 0
        for w in d[cur]:
            if w == target:
                return
                 level+1
            else:
                q.append((w, level+1))


print(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
  • No Image

4. 여행경로

  • 주어진 항공권 모두 이용하여 여행경로 짜기.
  • 공항들이 정점이 되고, 항공권이 간선이 된다.

  • 알파벳 순서를 지키는, 한붓 그리기 문제

  • DFS를 응용해야 한다.
  • 한붓그리기가 가능함은 문제에서 보장되어있다.
  • 시작 정점은 언제나 “ICN”
  • 모든 정점 방문이 아닌 모든 간선을 거치는게 목적이다.

  • 한 정점에서 택할 수 있는 간선이 두개 이상인 경우? -> 공항 이름의 알파벳 순서를 따른다.

  • 그래프를 어떻게 표현할까? -> 사전을 이용해서, 각 공항에서 출발하는 항공권의 집합을 표현
  • ICN -> {ATL,SFO}
  • 그런데 알파벳 순서가 중요했으니, 항공권을 알파벳 순서의 리스트로 표현하겠다.
  • 리스트 뒤에서 원소를 제거하는게 효율적이므로, 알파벳의 역순으로 정렬을 해서, 사용하겠다.
def solution(tickets):
    routes = dict()
    for t in tickets:
        routes[t[0]] = routes.get(t[0], []) + [t[1]]
    for r in routes:
        routes[r].sort(reverse=True)
    print(routes)
    stack = ["ICN"]
    path = []  # 가려는 경로
    while stack:
        top = stack[-1]
        if top not in routes or len(routes[top]) == 0:
            path.append(stack.pop())
        else:
            stack.append(routes[top][-1])  # 역순이니 이게 가장 알파벳 순서가 앞설거야
            # routes[top] = routes[top][:-1]  # pop을 적용해도 상관 없다.
            routes[top].pop()
    return path[::-1]


print(solution([["ICN", "SFO"], ["ICN", "ATL"], [
      "SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]))
  • No Image

참고자료 [프로그래머스]https://programmers.co.kr/learn/challenges [파이썬 문자열 비교]https://webisfree.com/2017-08-23/python%EC%97%90%EC%84%9C-match-string-%EC%9D%BC%EC%B9%98%ED%95%98%EB%8A%94-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%B0%BE%EB%8A%94-%EB%B0%A9%EB%B2%95 [참고 블로그]https://codedrive.tistory.com/78 [DFS]https://blog.ilkyu.kr/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89Depth-First-Search%EA%B3%BC-%EA%B5%AC%ED%98%84-%EB%B0%A9%EB%B2%95

0%