소민's Blog

1753. 최단 경로 내 풀이양수의 가중치를 가지는 방향 그래프 -> 다익스트라from collections import deque, defaultdictimport heapqv, e = map(int, input().split())point = int(input())graph = defaultdict(list)for _ in range(e): start, end, val = map(int, input().split()) graph[start].append((end, val))dist = [float('inf') for _ in range(v+1)]def dijkstra(start): queue = [] heapq.heappush(queue, (0, start)) dist[st..

다단계 칫솔 판매 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이각각의 판매원을 key, 추천인을 value 로 넣어두고판매 내역을 하나씩 확인하면서판매값*0.1이 1 미만일 때까지 추천인 타고가면서 배분 도중에 break 안걸어주면 시간초과from collections import deque,defaultdictdef solution(enroll, referral, seller, amount): answer = [] reference=defaultdict(list) money=defaultdict(int) for e,r in zip(enroll,referral): if..

거리두기 확인하기 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이거리 2내의 값들만 돌면서 확인파티션이 있으면 돌지 xfrom collections import dequedef solution(places): answer = [] dx=[-1,1,0,0] dy=[0,0,-1,1] def bfs(i,j,graph): queue=deque([(i,j)]) visited=[[-1 for _ in range(5)] for _ in range(5)] visited[i][j]=0 while queue: ..

숨바꼭질 3 문제 조건알고리즘모든 비용이 같음 (1)BFS가중치가 서로 다름다익스트라가중치가 0 또는 10-1 BFS (덱 사용) 내 풀이처음엔 순서대로 진행되는 dp라고 생각했지만 cur-1 처리가 안됨 한 위치에서 x-1, x+1, 2*x 가 다 처리된 뒤에 다음 위치꺼 처리해야하므로 bfs k가 넘어도 다시 돌아올 수 있음 → 조건 범위 맞춰서 100000 으로 크기 설정from collections import dequen,k=map(int,input().split())dp=[float('inf') for _ in range(100001)]def bfs(cur): queue=deque([cur]) dp[cur]=0 while queue: cur=queue.popleft..

리코쳇 로봇 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이 - BFS벽이나 장애물에 부딪칠때까지 while문으로 이동부딪치면 그 전 위치 반납하는게 일반 dfs와 차이가장 먼저 return 된게 가장 최단거리from collections import dequedef solution(board): board = [list(b.rstrip()) for b in board] n = len(board) m = len(board[0]) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] visited = [[False] * m for _ in rang..

무인도 여행 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이BFS bfs로 하나의 섬 돌면서 합을 tmp로 구한 후에 한번에 return from collections import dequedef solution(maps): answer = [] graph = [] for map in maps: graph.append(list(map)) n = len(graph) m = len(graph[0]) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(i, j): tmp = int(grap..

11725.트리의 부모 찾기  내 풀이union-find로 풀려고함근데 뒤에서 바뀌는 부모를 처리못해서 fail 풀이bfs로 루트 1부터 시작해서 자식노드에 해당 부모를 순서대로 넣어주면 되는 간단한 문제였다..!from collections import deque,defaultdictn=int(input())parents=[i for i in range(n+1)]graph=defaultdict(list)for _ in range(n-1): a,b=map(int,input().split()) graph[a].append(b) graph[b].append(a)def bfs(): queue=deque([1]) visited=[False for _ in range(n+1)] v..

부대복귀 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  내 풀이 여러 출발점에서 각각 최단 경로를 찾으면, 출발점마다 dijkstra 수행해야 하므로 매우 비효율적 O((V+E)*V)도착지는 동일한데 각각의 출발점과의 거리를 찾는 것⇒ 도착지를 시작점으로 다른 지점까지의 거리를 찾으면 한번만 돌면됨from collections import defaultdictimport heapqdef solution(n, roads, sources, destination): answer = [] graph=defaultdict(list) for road in roads: s,e=..

지게차와 크레인 [0] 으로 그래프 한바퀴 두르고 체크문자열 길이 2이상이면 crane으로 그냥 해당 문자 전부 다 지우기문자열 길이 1이면 외부 컨테이너만 지우기 from collections import dequedef solution(storage, requests): n=len(storage) m=len(storage[0]) answer = n*m graph=[] for st in storage: graph.append(list(st.strip())) visited=[[False for _ in range(m+2)] for _ in range(n+2)] for i in range(n+2): for j in rang..

배달 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이다익스트라 기본 문제from collections import dequedef solution(N, road, K): answer = 0 distance=[float('inf') for _ in range(N+1)] graph=[[] for _ in range(N+1)] for a,b,c in road: graph[a].append((b,c)) graph[b].append((a,c)) def bfs(start): queue=deque() distance[start]..