[네이버 코테 준비] 알고리즘 스터디 7일차

핵심

• 최단거리 탐색은 BFS(큐)로! (DFS는 스텍으로)
• 큐, 스택은 list말고 deque(데크) 사용하기! 
• 문자열 지정 문자 찾기 .index('x'), .rindex('x')
• 이진화: bin(x), 십진화 : int(x, 2)

 

1. 게임 맵 최단 거리

최단거리 탐색은 항상 BFS(넓이 우선 탐색)으로.
DFS(깊이 우선 탐색)으로 했다간 긴 경로를 짧은 경로로 인식할 수 있다.

 

<간단한 그래프 탐색 구현 예시>

myGraph = {
    'A': ['B'],
    'B': ['A', 'C', 'H'],
    'C': ['B', 'D'],
    'D': ['C', 'E', 'G'],
    'E': ['D', 'F'],
    'F': ['E'],
    'G': ['D'],
    'H': ['B', 'I', 'J', 'M'],
    'I': ['H'],
    'J': ['H', 'K'],
    'K': ['J', 'L'],
    'L': ['K'],
    'M': ['H']
}

<DFS>

from collections import deque

def my_dfs(graph, start_node):
    visited = list() # 방문한 노드를 담을 배열
    stack = deque([start_node]) # 정점과 인접한 방문 예정인 노드를 담을 배열
    # 처음에는 시작 노드 담아주고 시작하기.

    while stack: # 더 이상 방문할 노드가 없을 때까지.
        node = stack.pop() # 방문할 노드를 앞에서 부터 하나씩 꺼내기.

        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node) # visited 배열에 추가
            stack.extend(graph[node]) # 해당 노드의 자식 노드로 추가(오른쪽부터 탐색)
            # stack.extend(reversed(graph[node])) #왼쪽부터 탐색 

    print("dfs - ", visited)
    
# 함수 실행
my_dfs(myGraph, 'G')

# 출력 결과
dfs -  ['G', 'D', 'E', 'F', 'C', 'B', 'H', 'M', 'J', 'K', 'L', 'I', 'A']

<BFS>

def my_bfs(graph, start_node):
    visited = list() # 방문한 노드를 담을 배열
    queue = deque([start_node]) # 방문 예정인 노드를 담을 배열.
    # 처음에는 시작 노드 담아주고 시작하기.

    while queue: # 더 이상 방문할 노드가 없을 때까지.
        node = queue.popleft() # 방문할 노드를 앞에서 부터 하나씩 꺼내기.

        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node) # visited 배열에 추가
            queue.extend(graph[node]) # 해당 노드의 자식 노드로 추가
    
    print("bfs - ", visited)
    
# 함수 실행
my_bfs(myGraph, 'G')

# 출력 결과
bfs -  ['G', 'D', 'C', 'E', 'B', 'F', 'A', 'H', 'I', 'J', 'M', 'K', 'L']

 

 

https://cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html

[Daily PS] 파이썬으로 구현하는 BFS와 DFS

https://chaewonkong.github.io/posts/python-deque.html

 

Python - 데크(deque) 언제, 왜 사용해야 하는가?

 

<시도 답변>

dfs로 답변을 제출한 경우

채점 결과

정확성: 39.8

효율성: 0.0

합계: 39.8 / 100.0

 

<통과 답변>

from collections import deque

def solution(map):
    n, m = len(map), len(map[0])
    
    # Initialize the visited matrix and the queue for BFS
    visited = set()
    queue = deque([(0, 0, 1)])  # (row, col, steps)
    
    while queue:
        row, col, steps = queue.popleft()
        
        # Check if we've reached the target location
        if row == n-1 and col == m-1:
            return steps
        
        # Check if we've already visited this location
        if (row, col) not in visited:
          visited.add((row, col))
        else:
            continue
        
        # Try moving to adjacent cells
        for r, c in ((row-1, col), (row+1, col), (row, col-1), (row, col+1)):
            # Check if the new position is inside the map bounds and has not been visited before
            if 0 <= r < n and 0 <= c < m and (r, c) not in visited and map[r][c] != 0:
                queue.append((r, c, steps+1))
    
    # If we reach this point, there is no path to the target location
    return -1

 

2. 2개 이하로 다른 비트 

 

초기 접근

• 오른쪽에 0이 있는 경우, 가장 오른쪽 0에 1 더하기
• 오른쪽에 0이 없고, 오른쪽에서부터 1이 끝나는 지점에서 1, 0 교체하기 

-> 너무 복잡.. 좀 더 단순한 방법이 없을까?

 

솔루션

• 짝수일 경우, 무조건 마지막에 0으로 끝나므로, 1 더하기
• 홀수일 경우, 가장 뒤쪽에 있는 0을 1로 바꿔주고 그다음 비트를 0으로 바꿔주면 된다.
• 예를 들어 7(0111) 은 가장 뒤쪽에 있는 0을 1로 바꿔주고 그다음 비트를 0으로 바꿔준다. 즉, 11(1011)이 답이다.
• 그리고 9(1001) 은 1001 -> 1011 -> 1010 으로 10이 답이다.

def solution(numbers):
    answer = []
    for num in numbers:
        if num % 2 == 0 : #짝수
            answer.append(num+1)
        else:#홀수
            n = '0' + bin(num)[2:]
            n_0 = n.rindex('0')
            max_num = n[:n_0]+'10'+n[n_0+2:]
            answer.append(int(max_num, 2))
    return answer

 

3. 다리를 지나는 트럭

이 문제 푸는 데 좀 오래 걸렸는데.. 풀기 위한 발상을 한다면

2번째 예시 케이스에서 다리의 길이가 10이고 트럭이 1개가 주어진대도 결국에는 11초가 걸려야 한다는 점

*0으로 채워진 bridge_length 길이의 다리가 있다.

*다리에 트럭이 나갈때마다 나갔을 때 총 무게를 측정한다.

*다리에 트럭이 올라갈때 다리 무게 만족하는지 보고 조건에 따라 트럭을 다리위에 올려놓는다.

* 다리 위 총 무게를 측정한다. 

from collections import deque

def solution(bridge_length, weight, truck_weights):
    waiting_trucks = deque(truck_weights)
    on_bridge = deque([0]*bridge_length) 
    sec = 0
    on_bridge_w = 0
    while on_bridge and waiting_trucks:  
        #한칸씩 지날때마다 시간은 항상 흐르고 있음. 
        sec += 1
        #다리를 지나갔으므로 무게에서 제외..
        on_bridge_w -= on_bridge.popleft()
        if on_bridge_w+waiting_trucks[0] <= weight:
            truck = waiting_trucks.popleft()
            on_bridge.append(truck)
            on_bridge_w += truck
        else:
            on_bridge.append(0)
            
    # 마지막 트럭은 다 지나갈때까지 다리길이만큼 가야함. 
    return sec+bridge_length