MST 문제https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr💡풀이코드 (성공 - MST Kruskal)def solution(n, costs): answer = [] graph = [] ans = 0 for n1, n2, w in costs: graph.append((w, n1, n2)) parent = [0] * (n + 1) def init(): for i in range(1, n + 1): parent[i..

BFS 문제https://www.acmicpc.net/problem/2583💡 풀이코드 (Python3 성공)import sys from collections import deque m, n, k = map(int, sys.stdin.readline().split())visited = [[False] * (n) for _ in range(m)]dy = [1, 0, -1, 0]dx = [0, 1, 0, -1]def bfs(y, x): queue = deque() cnt = 0 queue.append((y, x)) visited[y][x] = True while queue: y, x = queue.popleft() cnt += 1 for ii..

그래프, BFS/DFS 문제https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 풀이코드 (성공 - MST Prim)import heapqdef solution(n, computers): answer = 0 graph = [[] for _ in range(len(computers) + 1)] # graph 만들기 for i in range(len(computers)): for j in range(len(computers)): ..

MST 문제https://www.acmicpc.net/problem/1647접근 방식문제 분석마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.-> N개의 노드와 M개의 간선을 가지는 양방향의 가중치 그래프일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다.-> MST (1. 불필요한 간선 제거 2. 최소 신장 ..

BFS 문제https://www.acmicpc.net/problem/9019시간 초과1. 문자열 변환 및 조작 연산은 느리다.문자열 변환문자열 변환(정수 -> 문자열 -> 정수)이 빈번하게 발생하면 누적된 비용이 상당히 커질 수 있다.문자열 슬라이싱슬라이싱 연산은 새로운 문자열을 생성하는 작업이므로, 메모리 할당 및 복사가 발생하며 매우 느린 작업이다.문자열 슬라이싱의 시간 복잡도는 O(k)로 비용이 크다. 이 때, k는 슬라이스된 문자열의 길이이다. 문자열 코드 (시간 초과 + 오답)while queue: val, dslr = queue.popleft() if val not in visited: visited.add(val) queue.append(((2 * val)..

그래프, BFS/DFS 문제https://www.acmicpc.net/problem/21736 💡 풀이코드 (성공 - DFS 1)import sys sys.setrecursionlimit(10 ** 9) r, c = map(int, sys.stdin.readline().split())graph = []start = []visited = [[False] * c for _ in range(r)]dy = [0, -1, 0, 1]dx = [1, 0, -1, 0]cnt = 0for i in range(r): l = list(sys.stdin.readline().strip()) for j in range(c): if l[j] == "I": start.append((i,..