3주차

네트워크

def dfs(node, computers, visited):
    visited[node] = True
    for i, neighbor in enumerate(computers[node]):
        if neighbor > 0 and i != node and visited[i] == False:
            dfs(i, computers, visited)
    return visited

def solution(n, computers):
    graph = [0]*n
    start = 0
    answer = 1
    while 1: 
        graph = dfs(start, computers, graph)
        if 0 in graph:
            start = graph.index(0)
            answer += 1
        else:
            break
    return answer 
        
    

게임맵 최단거리

from collections import deque

def solution(maps):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    row, col = len(maps), len(maps[0])
    q = deque([(0,0)])

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < col and 0 <= ny < row and maps[ny][nx] == 1:
                q.append((nx, ny))
                maps[ny][nx] = maps[y][x] + 1   

    return maps[row-1][col-1] if maps[row-1][col-1] != 1 else -1

단어변환

from collections import deque
 
def count_matches(str1, str2):
    count = len(str1)
    for char1, char2 in zip(str1, str2):
        if char1 == char2:
            count -= 1
    return True if count == 1 else False

def solution(begin, target, words): 
    degree = 0
    q = deque()  
    q.append([begin, []])
    
    while q:
        cur, visited = q.popleft()
        if cur == target:
            return len(visited)
        for word in words: 
            if count_matches(cur, word) and word not in visited:
                tmp = visited[0:]
                tmp.append(word)
                q.append([word, tmp])
    return 0

타겟넘버

from collections import deque

op = [-1, 1]

def solution(numbers, target):
    answer = 0
    q = deque([numbers[0], []])
    while q:
        res = 0
        t, visited = q.popleft()
        for i in range(2):
            res += t * op[i]
            if res == target:
                answer += 1
            
    return answer

아직푸는중중중

여행 경로

1트

from collections import deque

tickets = [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] 
tickets1 = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]


def solution(tickets):

    # d = {dep: sorted({arr for _, arr in tickets if _ == dep}) for dep, _ in tickets}
    d = {} 
    for dep,arr in tickets:
        d.setdefault(dep, set()).add(arr)
        d.setdefault(arr, set()).add(dep) 

    for key in d:
        d[key] = sorted(d[key]) 
    
    q = deque(["ICN"])
    visited = [] 
    while q:
        dep = q[-1] 
        if dep not in d or len(d[dep]) == 0:
            visited.append(q.popleft()) # already visited
        else:
            q.append(d.get(dep).pop(0))
         

    # tc 1. ["ICN", "JFK", "HND", "IAD"]
    # tc 2. ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
print(solution(tickets))

최종

def solution(tickets):
    tickets.sort(reverse=True) # 정렬
    path = {}

    for dep, arr in tickets:
        if dep in path:
            path[dep].append(arr)
        else:
            path[dep] = [arr]
    
    st = ['ICN']
    ans = []
    
    while st:
        dep = st[-1]

        if dep not in path or len(path[dep])==0:
            ans.append(st.pop())
        else: 
            st.append(path[dep].pop())

    return ans[::-1]

if dep not in path or len(path[dep])==0: ans.append(st.pop()) 다음으로 갈 수 없는 놈을 반환한다