bright

def solution(tickets):

    routes = dict()

    for t1, t2 in tickets:
        if t1 in routes:
            routes[t1].append(t2)
        else:
            routes[t1] = [t2]
    
    for r in routes.keys():
        routes[r].sort(reverse=True)

    st = ['ICN']
    ans = []
    while st:
        top = st[-1]
        if top not in routes or len(routes[top])==0:
            ans.append(st.pop())
            
        else:
            st.append(routes[top].pop())

    ans.reverse()
    return ans

... 아직 dfs-bfs 가 익숙하지 않다.  엄청 어렵다. 

step 1 ) 갈 수 있는 경로를 정의 한 routes 딕셔너리를 만든다. 

step 2 ) 문제에서 가능한 알파벳 순으로 나열하라고 했으므로 정렬한다. 이 때, 역으로 정렬하여 pop 했을 때 

           알파벳 순서가 빠른 곳이 먼저 나오도록 한다. 

step 3 ) 시작점은 'ICN' 이다. 

step 4 ) 문제에서 무조건 다 사용할 수 있다고 했으므로, 다음과 같은 알고리즘을 적용할 수 있다. 

           만약 내가 가려는 곳이 routes 에 존재하지 않는다면 ans 에 넣는다. 마지막에 다른 곳에서 이곳에 도착할 

           것이 분명하다.  존재한다면 다음 목적지로 삼으면 된다. 

Reference 

아래 블로그를 참고했음. 설명이 잘 되어있다. 

https://gurumee92.tistory.com/165

from collections import deque

def solution(begin, target, words):

    dist = {begin: 0}
    queue = deque([begin])

    while queue:
        current = queue.popleft()

        next_words = []

        for i in words:
            diff = 0 
            for j in range(len(begin)) :
                if i[j] != current[j]:
                    diff += 1 
            
            if diff == 1 : 
                next_words.append(i)

        for next_word in next_words:
            if next_word not in dist:
                dist[next_word] = dist[current] + 1
                queue.append(next_word)

    return dist.get(target, 0)

1. 분류 : BFS 

2. 풀이 방법 

step 1) bfs 알고리즘을 구현하기 위하여 deque 를 사용한다. 

step 2 ) dist = { 단어 : 변환한 수 } 를 표현하는 딕셔너리 이다.  처음에 begin 을 넣고 deque 에도 begin 을 넣는다. 

step 3 ) current 는 지금 검증할 단어이다. 

           -> 만약 current 와 알파벳 1개 차이가 나는 단어가 있다면 next_words 배열에 넣는다.

step 4 ) next_words 가 전에 바뀌었던 단어가 아니라면, dist 와 queue 에 넣어 준다. 

=> 4 단계 까지 오게 되면 모든 단어 변환을 거친다. 

step 5 ) 만약 dist 에 target 이 있다면 ( 변환 가능함을 의미 ) 변환 한 수를 출력하고, 없다면 0 ( default ) 를 출력한다. 

+ tip )  딕셔너리의 get method 

딕셔너리.get( key[ , defualt 값 ] ) 

: 딕셔너리에 key 가 있으면 해당 key의 value를 반환하고, 없으면 default에 지정한 값을 반환한다. 

default 생략 시, 아무런 값도 ( None ) 반환하지 않는다. 

def dfs(graph, v, visited. n) : 
    tmp = 0 
    if not visited[v] :
        visited[v] = True
        for i in range( n ):
            if graph[v][i] :
                dfs(graph, i, visited)
                tmp += 1 
        
        if tmp >= 1 : return True
    return False

def solution(n, computers):

    visited = [False] * n
    answer = 0

    for i in range(n):
        if dfs(computers, i , visited, n ): 
            answer += 1 
    return answer

step 1) 전에 방문한 적 없으면 -> 방문 처리  / 방문한 적 있으면 바로 return False 

step 2 ) 나랑 연결된 것 중에 -> 방문한 것 없는지 찾기 / 방문한 적 없는 것이 하나도 없으면 return False . 

                                                                          하나라도 방문 하지 않은 것이 있으면 return True 

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

numbers 안의 값은 더해지거나 빼지거나 2가지 경우의 수를 갖는다. 

모든 numbers 에 대하여 각 경우의 수를 더해 나가면 모든 경우의 수를 가질 수 있다. 

programmers.co.kr/learn/courses/30/lessons/43165

import itertools

L, c = map(int,input().split()) # 암호 길이, 문자의 수 
data = list(map(str,input().split()))
data.sort()

# c 개 중에 L 개 뽑아 나열하기 
# 최소 모음 1개 최수 2개 자음 

vowel = [ 'a', 'e', 'i', 'o', 'u']

for i in itertools.combinations( data,L):

    cnt = 0 

    for k in i : 
        if k in vowel:
            cnt += 1 
    
    if cnt >= 1 and cnt <= L-2 : 
        print( ''.join( i ))

풀이 방법 : 조합 ( combination ) 사용  /  import itertools 

L 개 중, c 개의 문자를 뽑아 암호를 만든다. 문제에서 순서는 알파벳 순이라고 지정해 주었으므로 

순열 ( permutations ) 가 아닌 조합을 사용하면 된다. 

암호의 조건으로 모음이 최소 1개, 자음이 최소 2개이다. 

따라서, 우선 가능한 조합을 모두 나열한 다음,

모음을 세는 변수를 만들어 암호 안의 모음의 개수를 세고 이를 활용하여 자음의 개수 까지 센다. 

( 모음이 아닌 건 다 자음이므로 모음의 수가 ( 전체 암호 길이 ) - 2 이하라면 조건을 만족한다 )