몸풀기 문제

깊이 우선 탐색 순회

해당 문제는 가장 기본적인 DFS 문제라 생각된다. 사실 문제에서 요구하는 바는 그냥 Node 를 탐색하는 순서만 List 로 반환하면 되지만, 나는 그냥 연습할 겸, 호출되는 재귀의 수도 같이 포함해서 출력해주었다.

def solution(edges, start):  
    graph = {}  
    check = set()  
    for vertext1, vertext2 in edges:  
        graph[vertext1] = graph.get(vertext1, [])  
        graph[vertext1].append(vertext2)  

    recursive_cnt = 0  
    answer = []  
    def dfs(vertext):  
        nonlocal recursive_cnt  
        recursive_cnt += 1  
        check.add(vertext)  
        answer.append(vertext)  
        for next_vertexts in graph.get(vertext, []):  
            for next_vertext in next_vertexts:  
                if next_vertext not in check:  
                    dfs(next_vertext)  

    dfs(start)  
    return answer, recursive_cnt  

print(solution([['A', 'B'], ['B', 'C'], ['C', 'D'], ['D', 'E']], 'A'))  
print(solution([['A', 'B'], ['A', 'C'], ['B', 'D'], ['B', 'E'], ['C', 'F'], ['E', 'F']], 'A'))

너비 우선 탐색 순회

인접리스트 + bfs (1)

사실 해당문제도 책의 그래프 탐색 거의 제일 앞부분에 나와있는만큼 기본적인 BFS 문제라고 생각된다. 해당 문제는 인접리스트 방법으로 Graph 를 표현하여 해결하였다.

정확히는 아래와 같은 Flow 로 코드를 구현하였다.

우선 입력값으로 들어온 Edge 정보들을 통해 정점(Vertext) 의 최대개수를 구하였다.
그다음 인접리스트 방식으로 Graph 를 정의함과 동시에 Visit 한 정점을 체크하기위해 check 배열도 정의해주었다.
이제 queue 에 탐색할 Vertext 를 넣어줌과 동시에 해당 Vertext 를 Visit 해주고, queue 로 탐색을 시작한다.
queue 안에서는 현재 Vertext 에서 갈 수 있는 또 다른 Vertext 들을 탐색하고, 탐색된 Vertext 는 answer 에 추가해주고 Visited 처리를 하고 queue 에 넣어준다.

from collections import deque  

def solution(edges, start):  
    vertext_cnt = -float('inf')  
    for vertexts in edges:  
        vertext_cnt = max(vertexts)  

    graph = [[] * (vertext_cnt + 1) for _ in range(vertext_cnt + 1)]  
    check = [0] * (vertext_cnt + 1)  
    for vertext1, vertext2 in edges:  
        graph[vertext1].append(vertext2)  

    answer = [start]  
    queue = deque([start])  
    check[start] = 1    
    while queue:  
        curr_vertext = queue.popleft()  
        for next_vertext in graph[curr_vertext]:  
            if not check[next_vertext]:  
                check[next_vertext] = 1  
                answer.append(next_vertext)  
                queue.append(next_vertext)  

    return answer  

print(solution([(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 8), (5, 8), (6, 9), (7, 9)], 1))  
print(solution([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)], 1))

인접리스트 + bfs (2)

해당 코드는 인접리스트 방법 (1) 와 answer 는 동일하게 출력하되 공부하는 입장에서 탐색한 총 Node 의 수 그리고 그래프(트리) 의 총 Level 까지 함께 출력되도록 구현한 것이다.

from collections import deque  

def solution(edges, start):  
    vertext_cnt = -float('inf')  
    for vertexts in edges:  
        vertext_cnt = max(vertexts)  

    graph = [[] * (vertext_cnt + 1) for _ in range(vertext_cnt + 1)]  
    check = [0] * (vertext_cnt + 1)  
    for vertext1, vertext2 in edges:  
        graph[vertext1].append(vertext2)  

    answer = [start]  
    queue = deque([start])  
    check[start] = 1  
    node_cnt = 1  
    bfs_depth = 0  
    while queue:  
        cnt = len(queue)  
        for _ in range(cnt):  
            curr_vertext = queue.popleft()  
            for next_vertext in graph[curr_vertext]:  
                if not check[next_vertext]:  
                    node_cnt += 1  
                    check[next_vertext] = 1  
                    answer.append(next_vertext)  
                    queue.append(next_vertext)  
        bfs_depth += 1  

    return f"""  
Visit Sequence : {answer}  
Total Node Count : {node_cnt}  
BFS Depth : {bfs_depth}  
"""  

print(solution([(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 8), (5, 8), (6, 9), (7, 9)], 1))  
print(solution([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)], 1))

인접행렬 + bfs

from collections import deque  

""" 인접행렬 + bfs """  
def solution(edges, start):  
    vertext_cnt = -100_000_000  
    for vertexts in edges:  
        vertext_cnt = max(vertexts)  

    graph = [[0] * (vertext_cnt + 1) for _ in range(vertext_cnt + 1)]  
    check = [0] * (vertext_cnt + 1)  
    for vertext1, vertext2 in edges:  
        graph[vertext1][vertext2] = 1  

    answer = [start]  
    queue = deque([start])  
    check[start] = 1  
    node_cnt = 1  
    bfs_depth = 0  
    while queue:  
        cnt = len(queue)  
        for _ in range(cnt):  
            curr_vertext = queue.popleft()  
            for next_vertext in range(vertext_cnt + 1):  
                if graph[curr_vertext][next_vertext] and not check[next_vertext]:  
                    node_cnt += 1  
                    check[next_vertext] = 1  
                    answer.append(next_vertext)  
                    queue.append(next_vertext)  
        bfs_depth += 1   
    return f"""  
Visit Sequence : {answer}  
Total Node Count : {node_cnt}  
BFS Depth : {bfs_depth}  
"""  

print(solution([(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 8), (5, 8), (6, 9), (7, 9)], 1))  
print(solution([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)], 1))

인접행렬 + dfs

풀긴했는데 현재 Node 까지의 거리를 이전 Node 의 거리 + 1 하여 distance 배열에 넣고 그 최대값이 그래프(트리) 의 차수가 되도록 풀었다.
(이게 맞나?)

""" 인접행렬 + dfs """  
def solution(edges, start):  
    vertext_cnt = -100_000_000  
    for vertexts in edges:  
        vertext_cnt = max(vertexts)  

    graph = [[0] * (vertext_cnt + 1) for _ in range(vertext_cnt + 1)]  
    check = [0] * (vertext_cnt + 1)  
    for vertext1, vertext2 in edges:  
        graph[vertext1][vertext2] = 1  

    distance = [0] * (vertext_cnt + 1)  
    answer = []  
    node_cnt = 0  
    def dfs(curr_vertext, previous_vertext):  
        nonlocal node_cnt  
        answer.append(curr_vertext)  
        distance[curr_vertext] = distance[previous_vertext] + 1  
        check[curr_vertext ] = 1  
        node_cnt += 1  
        for next_vertext in range(vertext_cnt + 1):  
            if graph[curr_vertext][next_vertext] and not check[next_vertext]:  
                dfs(next_vertext, curr_vertext)  

    dfs(start, start)  

    return f"""  
Visit Sequence : {answer}  
Total Node Count : {node_cnt}  
DFS Depth : {max(distance)}  
"""  

print(solution([(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 8), (5, 8), (6, 9), (7, 9)], 1))  
print(solution([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)], 1))

다익스트라

import heapq  

def solution(graph, start):  
    costs = {vertext: float('inf') for vertext in graph}  
    paths = {start: [start]}  

    costs[start] = 0  

    queue = []  
    heapq.heappush(queue, [costs[start], start])  

    while queue:  
        curr_cost, curr_vertext = heapq.heappop(queue)  
        if costs[curr_vertext] < curr_cost:  
            continue  
        for next_vertext, next_cost in graph[curr_vertext].items():  
            predicate_cost = costs[curr_vertext] + next_cost  
            if predicate_cost < costs[next_vertext]:  
                costs[next_vertext] = predicate_cost  
                paths[next_vertext] = paths[curr_vertext] + [next_vertext]  
                heapq.heappush(queue, [predicate_cost, next_vertext])  

    sorted_paths = {vertext: paths[vertext] for vertext in sorted(paths)}  

    return [costs, sorted_paths]  

print(  
    solution(  
        {  
            'A': {'B': 9, 'C': 3},  
            'B': {'A': 5},  
            'C': {'B': 1}  
        },  
        'A'  
    )  
)  
print(  
    solution(  
        {  
            'A': {'B': 1},  
            'B': {'C': 5},  
            'C': {'D': 1},  
            'D': {},  
        },  
        'A'  
    )  
)

벨만포드 알고리즘

우선 현재 Node 에서 갈 수 있는 다음 Node 들 중 최소 Cost 을 선택하는 것이 아니기 때문에, heapq 는 필요 없다는 것이다.

def solution(negative_graph, source):  
    vertext_cnt = len(negative_graph)                   # 그래프의 노드 수  
    costs = [float('inf')] * vertext_cnt                # 거리 배열 초기화  
    predecessor = [[] for _ in range(vertext_cnt)]      # 직전 경로 배열 초기화  

    costs[source] = 0                           # 우선, 시작점의 거리를 0 으로 설정하고  
    predecessor[source] = [source]              # 시작점의 직전 경로를 [시작점] 으로 설정한다.  

    for _ in range(vertext_cnt - 1):                                # 최단거리를 갱신할 수 있는 간선의 최대 개수만큼 반복하여 최단 경로 갱신한다.  
        for curr_vertext in range(vertext_cnt):  
            for next_vertext, next_cost in negative_graph[curr_vertext]:  
                predicate_cost = costs[curr_vertext] + next_cost  
                if costs[next_vertext] > predicate_cost:            # 현재 노드 curr_vertext 를 거쳐서 노드 v로 가는 경로의 거리가 기존에 저장된 노드 next_vertext 까지의 거리보다 짧은 경우  
                    costs[next_vertext] = predicate_cost            # 최단 거리를 갱신해주고  
                    predecessor[next_vertext] = predecessor[curr_vertext] + [next_vertext]   # 직전 경로를 업데이트해준다  

    for curr_vertext in range(vertext_cnt):                         # 음의 가중치 순회 체크  
        for next_vertext, next_cost in negative_graph[curr_vertext]:  
            predicate_cost = costs[curr_vertext] + next_cost  
            if costs[next_vertext] > predicate_cost:                # 현재 노드 curr_vertext 를 거쳐서 노드 next_vertext 로 가는 경로의 거리가 기존에 저장된 노드 next_vertext 까지의 거리보다 짧은 경우  
                return [-1]                                         # 음의 가중치 순회가 발견되었으므로 [-1]을 반환합니다.  

    return [costs, predecessor]  


print(solution([[(1, 4), (2, 3), (4, -6 )], [(3, 5)], [(1, 2)], [(0, 7), (2, 4)],[(2, 2)]],0))  
print(solution([[(1, 5), (2, -1)], [(2, 2)], [(3, -2)], [(0, 2), (1, 6)]],0))

합격자가 되는 모의테스트

게임 맵 최단 거리 (BFS)

문제를 잘 읽어야한다고 느낀 문제.. 당연히 정사각형인줄 알았는데 아니었다. 삽질 (무려 1시간

방법 1 (check 배열 사용 X)

from collections import deque  

drow = [-1, 0, 1, 0]  
dcol = [0, 1, 0, -1]  

def solution(maps):  
    row_cnt = len(maps)  
    col_cnt = len(maps[0])  
    queue = deque()  
    distance = [[0] * col_cnt for _ in range(row_cnt)]  

    queue.append((0, 0))  
    distance[0][0] = 1  

    while queue:  
        row, col = queue.popleft()  
        if distance[row_cnt - 1][col_cnt - 1] != 0:  
            return distance[row_cnt - 1][col_cnt - 1]  
        for d in range(4):  
            nrow = row + drow[d]  
            ncol = col + dcol[d]  
            if (0 <= nrow < row_cnt) and (0 <= ncol < col_cnt) and (maps[nrow][ncol]):  
                if distance[nrow][ncol] == 0:  
                    distance[nrow][ncol] = distance[row][col] + 1  
                    queue.append((nrow, ncol))  

    return -1  

print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]))  
print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]))

방법 2 (check 배열 사용 O)

from collections import deque  

drow = [-1, 0, 1, 0]  
dcol = [0, 1, 0, -1]  

def solution(maps):  
    row_cnt = len(maps)  
    col_cnt = len(maps[0])  
    queue = deque()  
    check = set()  
    distance = [[0] * col_cnt for _ in range(row_cnt)]  

    queue.append((0, 0))  
    check.add((0, 0))  
    distance[0][0] = 1  

    while queue:  
        row, col = queue.popleft()  
        if distance[row_cnt - 1][col_cnt - 1] != 0:  
            return distance[row_cnt - 1][col_cnt - 1]  
        for d in range(4):  
            nrow = row + drow[d]  
            ncol = col + dcol[d]  
            if (0 <= nrow < row_cnt) and (0 <= ncol < col_cnt) and (maps[nrow][ncol]) and ((nrow, ncol) not in check):  
                distance[nrow][ncol] = distance[row][col] + 1  
                check.add((nrow, ncol))  
                queue.append((nrow, ncol))  

    return -1  

print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]))  
print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]))

방법 3 (기존 방문한 map 을 벽으로 바꿔가며 탐색)

from collections import deque  

drow = [-1, 0, 1, 0]  
dcol = [0, 1, 0, -1]  

def solution(maps):  
    row_cnt = len(maps)  
    col_cnt = len(maps[0])  
    queue = deque()  
    distance = [[0] * col_cnt for _ in range(row_cnt)]  

    queue.append((0, 0))  
    distance[0][0] = 1  
    maps[0][0] = 0  

    while queue:  
        row, col = queue.popleft()  
        if distance[row_cnt - 1][col_cnt - 1] != 0:  
            return distance[row_cnt - 1][col_cnt - 1]  
        for d in range(4):  
            nrow = row + drow[d]  
            ncol = col + dcol[d]  
            if (0 <= nrow < row_cnt) and (0 <= ncol < col_cnt) and (maps[nrow][ncol]):  
                distance[nrow][ncol] = distance[row][col] + 1  
                queue.append((nrow, ncol))  
                maps[nrow][ncol] = 0  

    return -1  

print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]))  
print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]))

네트워크

인접행렬 + dfs

def solution(n, computers):  
    vertext_cnt = n  

    check = [0] * vertext_cnt  
    def dfs(computer):  
        check[computer] = 1  
        for next_computer in range(vertext_cnt):  
            if computers[computer][next_computer] and not check[next_computer]:  
                dfs(next_computer)  

    answer = 0  
    for computer in range(vertext_cnt):  
        if not check[computer]:  
            answer += 1  
            dfs(computer)  

    return answer  

print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]))  
print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))  

"""  
idx 0 --> 1 1 0 : (0 --> 0)(0 --> 1)    
idx 1 --> 1 1 0 : (1 --> 0)(1 --> 1)  
idx 2 --> 0 0 1 : (2 --> 2)  

idx 0 --> 1 1 0 : (0 --> 0)(0 --> 1)  
idx 1 --> 1 1 1 : (1 --> 0)(1 --> 1)(1 --> 2)  
idx 2 --> 0 1 1 : (2 --> 1)(2 --> 2)  
"""

인접리스트 + dfs

def solution(n, computers):  
    vertext_cnt = n  
    graph = [[] for _ in (vertext_cnt)]  
    for computer, vertexts in enumerate(computers):  
        for vertext, value in enumerate(vertexts):  
            if value: graph[computer].append(vertext)  

    check = [0] * vertext_cnt  
    def dfs(vertext):  
        check[vertext] = 1  
        for next_vertext in graph[vertext]:  
            if not check[next_vertext]:  
                dfs(next_vertext)  

    answer = 0  
    for vertext in range(vertext_cnt):  
        if not check[vertext]:  
            answer += 1  
            dfs(vertext)  
            return answer  

print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]))  
print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))  

"""  
idx 0 --> 1 1 0 : (0 --> 0)(0 --> 1)    
idx 1 --> 1 1 0 : (1 --> 0)(1 --> 1)  
idx 2 --> 0 0 1 : (2 --> 2)  

idx 0 --> 1 1 0 : (0 --> 0)(0 --> 1)  
idx 1 --> 1 1 1 : (1 --> 0)(1 --> 1)(1 --> 2)  
idx 2 --> 0 1 1 : (2 --> 1)(2 --> 2)  
"""

인접행렬 + bfs

from collections import deque  

def solution(n, computers):  
    vertext_cnt = n  

    answer = 0  
    queue = deque()  
    check = [0] * vertext_cnt  
    for computer in range(vertext_cnt):  
        if not check[computer]:  
            check[computer] = 1  
            queue.append(computer)  
            while queue:  
                curr_computer = queue.popleft()  
                for next_comupter in range(vertext_cnt):  
                    if computers[curr_computer][next_comupter] and not check[next_comupter]:  
                        check[next_comupter] = 1  
                        queue.append(next_comupter)  
            answer += 1  

    return answer  

print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]))  
print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))  

"""  
idx 0 --> 1 1 0 : (0 --> 0)(0 --> 1)    
idx 1 --> 1 1 0 : (1 --> 0)(1 --> 1)  
idx 2 --> 0 0 1 : (2 --> 2)  

idx 0 --> 1 1 0 : (0 --> 0)(0 --> 1)  
idx 1 --> 1 1 1 : (1 --> 0)(1 --> 1)(1 --> 2)  
idx 2 --> 0 1 1 : (2 --> 1)(2 --> 2)  
"""

인접리스트 + bfs

from collections import deque  

def solution(n, computers):  
    vertext_cnt = n  
    graph = [[] for _ in range(vertext_cnt)]  
    for computer, vertexts in enumerate(computers):  
        for vertext, value in enumerate(vertexts):  
            if value: graph[computer].append(vertext)  

    check = [0] * vertext_cnt  
    queue = deque()  
    answer = 0  
    for computer in range(vertext_cnt):  
        if not check[computer]:  
            queue.append(computer)  
            check[computer] = 1  
            while queue:  
                curr_computer = queue.popleft()  
                for next_computer in graph[curr_computer]:  
                    if not check[next_computer]:  
                        check[next_computer] = 1  
                        queue.append(next_computer)  
            answer += 1  

    return answer  

print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]))  
print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))  

"""  
idx 0 --> 1 1 0 : (0 --> 0)(0 --> 1)    
idx 1 --> 1 1 0 : (1 --> 0)(1 --> 1)  
idx 2 --> 0 0 1 : (2 --> 2)  

idx 0 --> 1 1 0 : (0 --> 0)(0 --> 1)  
idx 1 --> 1 1 1 : (1 --> 0)(1 --> 1)(1 --> 2)  
idx 2 --> 0 1 1 : (2 --> 1)(2 --> 2)  
"""

배달 (인접리스트 + 다익스트라)

import heapq  

def solution(N, road, K):  
    houst_cnt = N  
    houses = [[] for _ in range(houst_cnt + 1)]  
    for house1, house2, time in road:  
        houses[house1].append([house2, time])  
        houses[house2].append([house1, time])  

    times = [float('inf') for _ in range(houst_cnt + 1)]  
    paths = [float('inf') for _ in range(houst_cnt + 1)]  

    times[1] = 0  
    paths[1] = [1]  

    queue = []  
    heapq.heappush(queue, [times[1], 1])  
    while queue:  
        curr_time, curr_house = heapq.heappop(queue)  
        if curr_time < times[curr_house]:  
            continue  
        for next_house, next_cost in houses[curr_house]:  
            predicate_time = curr_time + next_cost  
            if predicate_time < times[next_house]:  
                times[next_house] = predicate_time  
                paths[next_house] = paths[curr_house] + [next_house]  
                heapq.heappush(queue, [predicate_time, next_house])  

    return sum([1 for time in times if time <= K])  

print(solution(5, [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]], 3))  
print(solution(6, [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]], 4))

경주로 건설

(아직 못풀어본 문제. 백준에서 굴러보고 풀어볼 예정)

전력망을 둘로 나누기

(아직 못풀어본 문제. 백준에서 굴러보고 풀어볼 예정)