그래프

이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 11장 문제풀이입니다 실전 문제 게임 맵 최단거리 간선 가중치가 없는 케이스에서의 최단거리를 구해야하므로 아이디어로 BFS를 떠올리면 된다. 몇 가지 예외 처리 (좌표, 벽)과 방문 불가능한 케이스만 주의하면 전형적인 BFS 코드로 풀이 가능 from collections import deque from typing import List def solution(maps: List[List[int]]) -> int: def is_valid_coordinate(x: int, y: int) -> bool: return 0 int: graph = defaultdict(list) for u, v, w in road: graph[u].append((v, w))..

이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 11장 써머리입니다 그래프의 개념 노드와 간선을 이용한 비선형 자료 구조. 간선은 1) 무방향/유방향 2) 가중치 O/X 조합이 가능함 방향이 있는 그래프를 Directed Graph, 없는 그래프를 Undirected Graph 라고 한다 특정 노드에서 시작해 다시 돌아오는 경로가 있을 경우 Cycle (순혼)이 존재한다고 하며 Cycle Graph라고 함 그래프 구현 인접 행렬 인접 리스트 인접 행렬 구현은 배열을 주로 활용하며, 배열의 인덱스는 노드 그리고 값은 노드의 가중치로 볼 수 있다 반대로 인접 리스트 구현은 배열과 노드 객체를 이용해서 주로 표현함. 그러면 배열의 인덱스는 시작 노드를 의미하며 값에는 다음 노드를 연결할 수 있음 인접 ..