[프로그래머스] BFS/DFS 2문제

단어 변환

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

알고리즘

• bfs

코드

from collections import deque #deque import

def solution(begin,target,words):
    queue = deque()
    length = len(words)

    def can_change(word,change):
        diff = 0
        for i in range(len(word)):
            if word[i] != change[i]:
                diff += 1
        if diff == 1 : 
            return True
        else:
            return False

    def bfs():
        queue.append([begin ,0])#시작 단어와 깊이

        if target not in words:
            return 0

        while queue : 
            word,depth = queue.popleft() 
            for change in words:
                if can_change(word,change):
                    if change == target:
                        return depth+1
                    else:
                        queue.append([change,depth+1])

    answer = bfs()
    return answer

설명

가장 최소가 되는 단계를 구하는 문제이기 때문에 DFS가 아닌 BFS로 접근해서 문제를 해결해야함

• 문자열중에 하나만 변환할 수 있는 경우를 체크해야 한다.
• 큐에 초기값을 넣어준다.
  • 큐에서 word,depth 를 빼온다.
  • words 목록을 순회하면서 변경이 가능한 경우라면 큐에 추가한다.
    • 이때 가장 빨리 target 이 되는 경우가 최소 변환 과정이다.

어려웠던 점

• 문자가 하나만 다른걸 어떻게 체크하지?
• python queue 에 값 넣고 빼는거 연습좀 해야겠음
• 오늘도 온전히 내 힘으로 풀지 못했다 ㅜㅜ
• 딕셔너리를 쓸 수도 있다는데 그것까지 생각 + 알아보고 싶지않았다 (지침)

---

여행 경로

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

알고리즘

모든 노드를 탐색하고, 알파벳 순으로 우선순위 정렬이 필요해서 dfs,sort 라고 생각했다.

• dfs
• sort

코드

나의 최선...
def dfs(graph,v,visited):
    # 현재 노드를 방문처리
    visited[v] = True
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)



def solution(tickets):
    answer = []
    for i in len(tickets):
        if tickets[i][0] =='ICN':
            # result 에 추가 ..
            answer.append()
            dfs()


    return answer


----찐 답---
from collections import defaultdict
def solution(tickets):
    # 특정 티켓의 인접 리스트를 구하는 함수
    def init_graph():
        routes = defaultdict(list)
        for key, value in tickets:
            routes[key].append(value)
        return routes

    # 스택을 사용한 DFS
    def dfs():
        stack = ["ICN"]
        path = []  # 가려고하는 경로를 저장하는 변수
        while len(stack) > 0:  # stack이 비어있을 때까지
            top = stack[-1] 
            # 특정 공항에서 출발하는 표가 없다면 또는 있지만 티켓을 다 써버린 경우
            if top not in routes or len(routes[top]) == 0:
                path.append(stack.pop()) #스택에서 항공편을 꺼내서 경로에 추가합니다.
            else:
                stack.append(routes[top].pop(0)) #해당 항공편을 스택에 넣고, routes 딕셔너리에서 해당 항공편을 제거합니다.
        return path[::-1] #모든 경로를 찾은 후, 역순으로 뒤집어서 경로를 반환합니다.

    routes = init_graph()#init_graph 함수를 호출하여 항공표를 기반으로 인접 리스트(routes)를 생성
    for r in routes:
        routes[r].sort() #각 출발지에서 도착지로 가능한 여러 항공편이 있을 경우, 항공편을 알파벳 순서로 정렬합니다.

    answer = dfs() #dfs 함수를 호출하여 여행 경로를 찾고, 결과를 answer 변수에 저장합니다.
        return answer

설명

• (내가 생각한 로직)
  1. tickets 배열중 ICN 이 있다면 dfs 시작 + 방문배열에 추가 + result 배열에 값 추가
  2. ICN 노드의 두번째 인덱스와 일치하는 다른 노드 탐색
  3. 방문 여부 확인 → 방문 안했다면 두 배열에 추가 + 그 노드의 두번째 인덱스와 일치하는 다른 노드 탐색
  4. 계속 탐색하다가 더이상 탐색할게 없다면, 경로가 만약 여러개라면 알파벳 순으로 정렬해서 제일 우선인거를 출력
  5. 이걸 어케 구현하지..
• 정답 로직
  1. { 시작점 : [도착점], ... } 형태의 인접 리스트 그래프를 생성합니다.
  2. ‘도착점’의 리스트를 정렬합니다. (알파벳 순서로)
  3. DFS 알고리즘을 사용해 모든 점을 순회합니다. (스택이 빌때까지)
     • 스택에서 가장 위 데이터(top)를 가져옵니다.
     • 가져온 데이터(top)가 그래프에 없거나, 티켓을 모두 사용한 경우, path에 저장
     • 아니라면, 가져온 데이터(top)을 시작점으로 하는 도착점 데이터 중 가장 앞 데이터(알파벳순으로 선택해야하므로)를 가져와 stack에 저장
  4. path를 역순으로 출력 !

스택 방식(개념)

1. 탐색 시작 노드를 스택에 삽입하고 방문 배열에 방문 했다고 표시한다.
2. 스택의 최상단 노드에 방문 하지 않은 인접 노드가 있으면 해당 노드를 스택에 넣고 방문 처리를 한다.
3. 만약 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.
4. 2번과 3번 과정을 스택이 빌 때 까지 진행한다.

재귀 방식 (개념)

1. 탐색 노드를 시작으로 탐색했던 노드들은 모두 방문 배열에 방문 했다고 표시한다.
2. 탐색 중인 노드 주변으로 방문 하지 않은 노드를 찾는다.
   1. 있다면 그 인접 노드를 함수의 인자로 넣어 재귀적으로 동작하도록 한다.
   2. 없다면 종료한다.

이 문제에서는 방문하지 않은 인접 노드를 찾을 때 일치하는지의 여부에 따라 탐색이 가능한것 같다.

어려웠던 점

• 방문배열 구현하는 것
• 스택…쓰는거 어렵다.
• defaultdict() : 딕셔너리를 만드는 dict클래스의 서브 클래스이다.
  • 인자로 주어진 객체의 기본값을 딕셔너리값의 초기값으로 지정할 수 있다.
  • 이 문제에서는 디폴트값을 list인 딕셔너리로 지정했기때문에 빈 리스트로 초기화 되었다.
  • from collections import defaultdict # defaultdict 생성 my_dict = defaultdict(list) # 존재하지 않는 키에 접근하면 빈 리스트가 생성됨 my_dict['apple'].append('red') my_dict['banana'].append('yellow') print(my_dict)