[묘공단]코딩 테스트 합격자 되기(7주차) 그래프

Erdos·2024년 2월 20일

IT도서 코딩테스트

코딩테스트합격자되기-파이썬편

목록 보기

6/10

📖저자님의 책 소개 영상: https://www.youtube.com/watch?v=Q13Uj_5bH9M

🗓️TIL (this week I learned)
화 읽기, 정리가 까다로움🤔
수
목 몸풀기문제1
금 몸풀기문제
토 문제

11-2 그래프 탐색 ⭐⭐⭐

	깊이 우선 탐색 Depth-first search (DFS)	너비 우선 탐색 Breadth-first search (BFS)
참고	wiki(en) wiki(ko)	wikipedia(en) wiki(ko)
그림
특성	가장 깊은 노드까지 방문한 후에 더이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음, 해당 노드에서 방문할 노드가 있는지 확인한다.	시작 노드부터 인접한 노드를 모두 방문한 후 그다음 단계의 인접 노드를 방문(먼저 발견한 노드)
활용	🔹모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때 🔹그래프의 사이클을 감지해야 하는 경우	🔹미로 찾기에서 최단 경로를 찾을 때 🔹네트워크 분석 문제
장점	- 현 경로상의 노드를 기억하기 때문에 비교적 적은 메모리 - 목표노드가 깊은 단계에 있을 경우 해를 빨리 찾을 수 있음	- 가중치가 없는 그래프에서 최단 경로 보장 - 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리
단점	🔹해가 없는 경우 깊이 빠질 가능성 🔹얻은 해가 최적의 해가 아닐 수도 있음(해에 다다르면 탐색을 끝내므로)	🔹경로가 매우 길 경우 많은 저장 공간이 필요함 🔹해가 존재하지 않는 유한 그래프인 경우, 모든 그래프 탐색 후 실패로 끝남 🔹무한 그래프의 경우 해를 찾지도 못하고, 끝내지도 못함.

11-3 그래프 최단 경로 구하기

1. 다익스트라 알고리즘

🔹음의 가중치가 있는 그래프에서 다익스트라 알고리즘은 제대로 동작하지 않음.
🔹가장 좋은 것을 선택하는 전력을 가진 그리디 알고리즘 원리와 같음
🔹한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는다.

2. 벨만-포드 알고리즘

🔹매 단계마다 모든 간선의 가중치를 다시 확인하여 최소 비용 갱신, 음의 가중치를 가지는 그래프에서 최단 경로를 구할 수 있음.
🔹왜 정점 개수 -1만큼 반복하는가? 매 연산마다 최단 경로가 1개씩 확정되므로 ✅

🔹왜 한 번 더 연산을 반복하는가? 음의 순환을 찾기 위해!

🤔🤔🤔🤔

3. 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

🔹모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우에 사용하는 알고리즘

11-4 문제

1. 게임 맵 최단거리

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

from collections import deque

def solution(maps):
    move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    
    n = len(maps)
    m = len(maps[0])
    dist = [[-1] * m for _ in range(n)]
    
    def bfs(start):
        q = deque([start])
        dist[start[0]][start[1]] = 1
        
        while q:
            here = q.popleft()
            
            for direct in move:
                row, column = here[0] + direct[0], here[1] + direct[1]
                
                if row < 0 or row >= n or column < 0 or column >= m:
                    continue
                if maps[row][column] == 0:
                    continue
                if dist[row][column] == -1:
                    q.append([row, column])
                    dist[row][column] = dist[here[0]][here[1]] + 1
                    
        return dist
    bfs([0, 0])
        
    return dist[n-1][m-1]

조금 더 정리정돈 ⬇️

from collections import deque

def solution(maps):
    move = [(-1,0),(0,-1),(0,1),(1,0)]
    n, m = len(maps), len(maps[0])
    dist = [[-1]*m for _ in range(n)]
    
    def bfs():
        q = deque([(0,0)])
        dist[0][0] = 1
        
        while q:
            x,y = q.popleft()
            for dx,dy in move:
                nx, ny = x+dx, y+dy
                if 0 <= nx < n and 0 <= ny < m \
                   and maps[nx][ny] == 1 \
                   and dist[nx][ny] == -1:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx,ny))
        return dist
    
    bfs()
    return dist[n-1][m-1]

def solution(board):
    # 좌표가 범위 내 있는가
    def is_valid(x,y):
        return 0 <= x < N and 0 <= y < N
    
    #주어진 좌표가 이동할 수 있는가
    def is_blocked(x,y):
        return (x, y) == (0, 0) or not is_valid(x, y) or board[x][y] == 1
    
    #도로 건설 비용 계산
    def calculate_cost(direction, prev_direction, cost):
        if prev_direction == -1 or (prev_direction - direction) % 2 == 0:
            return cost + 100
        else:
            return cost + 600
    
    #주어진 좌표와 방향이 아직 방문하지 않았거나 새 비용이 더 작은 경우
    def isSouldUpdate(x, y, direction, new_cost):
        return visited[x][y][direction] == 0 or visited[x][y][direction] > new_cost
    
    queue = [(0,0,-1,0)]
    N = len(board)
    directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
    visited = [[[0 for _ in range(4)] for _ in range(N)] for _ in range(N)]
    answer = float("inf")
    
    while queue:
        x, y, prev_direction, cost = queue.pop(0)
        
        for direction, (dx, dy) in enumerate(directions):
            new_x, new_y = x + dx, y + dy
            
            if is_blocked(new_x, new_y):
                continue

            new_cost = calculate_cost(direction, prev_direction, cost)

            if (new_x, new_y) == (N - 1, N - 1):
                answer = min(answer, new_cost)
                
            # 좌표, 방향이 아직 방문하지 않았거나 새 비용이 더 적은 경우 큐에 추가    
            elif isSouldUpdate(new_x, new_y, direction, new_cost):
                queue.append((new_x, new_y, direction, new_cost))
                visited[new_x][new_y][direction] = new_cost

    return answer

우선순위 큐로 풀기 ⬇️

import heapq

def solution(board):
    N = len(board)
    directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]  # 좌, 상, 우, 하
    visited = [[[float("inf")] * 4 for _ in range(N)] for _ in range(N)]

    def is_valid_and_free(x, y):
        return 0 <= x < N and 0 <= y < N and board[x][y] == 0

    queue = []
    for d in range(4):
        visited[0][0][d] = 0
    heapq.heappush(queue, (0, 0, 0, -1))  # cost, x, y, 이전에 이동해온 방향(직선/코너)

    while queue:
        cost, x, y, prev_d = heapq.heappop(queue)

        for d, (dx, dy) in enumerate(directions):
            nx, ny = x + dx, y + dy
            if not is_valid_and_free(nx, ny):
                continue

            new_cost = cost + (100 if prev_d == -1 or (prev_d - d) % 2 == 0 else 600)

            if visited[nx][ny][d] > new_cost:
                visited[nx][ny][d] = new_cost
                heapq.heappush(queue, (new_cost, nx, ny, d))

    return min(visited[N-1][N-1])

5. 전력망을 둘로 나누기

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

def solution(n, wires):
    graph = [[] for _ in range(n + 1)]
    for a, b in wires:
        graph[a].append(b)
        graph[b].append(a)
        
    def dfs(node, parent):
        cnt = 1
        for child in graph[node]:
            if child != parent:
                cnt += dfs(child, node)
        return cnt

    min_diff = float("inf")
    for a, b in wires:
        graph[a].remove(b)
        graph[b].remove(a)

        cnt_a = dfs(a, b)
        cnt_b = n - cnt_a

        min_diff = min(min_diff, abs(cnt_a - cnt_b))

        graph[a].append(b)
        graph[b].append(a)
    return min_diff

[묘공단]코딩 테스트 합격자 되기(6주차) 집합

다음 포스트

[묘공단]코딩 테스트 합격자 되기(7주차) 그래프

코딩테스트합격자되기-파이썬편

11-2 그래프 탐색 ⭐⭐⭐

11-3 그래프 최단 경로 구하기

1. 다익스트라 알고리즘

2. 벨만-포드 알고리즘

3. 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

11-4 문제

1. 게임 맵 최단거리

2. 네트워크

3. 배달

4. 경주로 건설(고난이도)

5. 전력망을 둘로 나누기

추천문제

[묘공단]코딩 테스트 합격자 되기(6주차) 집합

[묘공단]코딩 테스트 합격자 되기(8주차) 백트래킹

0개의 댓글