목록코딩테스트/Graph (3)

수 많은 우문은 현답을 만든다

인접하지 않은 섬 개수 구하기

문제 주어진 m x n 크기의 2D 이진 그리드 grid는 '1'로 표시된 육지와 '0'으로 표시된 물의 지도를 나타냅니다. 섬의 수를 반환하는 함수를 작성하세요. 섬은 물로 둘러싸여 있으며 수평 또는 수직으로 인접한 육지를 연결하여 형성됩니다. 그리드의 네 가장자리는 모두 물로 둘러싸여 있다고 가정할 수 있습니다. Example: Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3 아주 신나고 흥미 진진한 문제네요~ 생각보다 쉽게 풀릴 것 같은데요 한 번 풀어보겠습니다. class Solution: def numIslands(self, grid..
코딩테스트/Graph 2024. 2. 1. 00:55
인접 그래프 최소 이동거리 구하기

문제 이번엔 찾고자하는 타겟 val 값이 가장 가까운 vertex 까지의 거의를 반환하는 문제이다. 풀이 def findShortest(graph_nodes, graph_from, graph_to, ids, val): cost = -1 graph = defaultdict(list) for i in range(0, len(graph_from)): graph[graph_from[i]].append(graph_to[i]) graph[graph_to[i]].append(graph_from[i]) visited = set() def bfs(start): visited.add(start) q = deque([[start, 0]]) # ([])를 쓰면 TypeError: cannot unpack non-iterabl..
코딩테스트/Graph 2024. 1. 25. 02:01
그래프 군집 구하기

문제 문제를 간략히 설명하자면, n 개의 city가 있고 여기에 도서관(lib)을 세워야하고 인접한 city에는 도서관이 하나만 있으면 되는데 이때 최소비용을 구하는 문제입니다. (너무 내용을 축약했기 때문에 상세 조건들은 문제를 보셔야합니다) 최초 아이디어 def roadsAndLibraries(n, c_lib, c_road, cities): while q: x, y = q.popleft() if x not in visited and y not in visited: # elif x not in visited or y in visited: # return min(n * c_lib, result) 리스트가 [[1,2], [3,4] ...] 이런 모양이기 때문에 x, y 요소를 얻어내어서 각 점이 방문했는지..
코딩테스트/Graph 2024. 1. 24. 00:03
이전 Prev 1 Next 다음