목록그래프 이론 (20)

기록하고 까먹지 말기

합승 택시 요금

날짜 : 2023. 10. 09 사용 언어 : python 문제 코드 다익스트라 import heapq INF = int(1e9) def solution(n, s, a, b, fares): graph = [[] for _ in range(n + 1)] for edge in fares: # 각 노드와 연결된 edge 체크 p, q, cost = edge graph[p].append([q, cost]) graph[q].append([p, cost]) def dijkstra(start, end): dist = [INF] * (n + 1) dist[start] = 0 # 현재노드 queue = list() heapq.heappush(queue, [0, start]) while queue: d, now = hea..
전공/프로그래머스 2023. 10. 9. 21:06
양과 늑대

날짜 : 2023. 10. 08 사용 언어 : python 문제 코드 def solution(info, edges): visited = [False] * len(info) # 방문처리 res = list() visited[0] = True res.append(1) def dfs(sheep, wolf): if sheep > wolf: res.append(sheep) else: return for start, end in edges: if visited[start] and not visited[end]: # 부모노드 방문 완료, 자식노드 탐색 visited[end] = True # 방문처리 if info[end] == 0: # 자식이 양 dfs(sheep + 1, wolf) else: dfs(sheep, w..
전공/프로그래머스 2023. 10. 8. 10:43
무인도 여행

날짜 : 2023. 10. 06 사용 언어 : python 문제 코드 from collections import deque def solution(graph): n, m = len(graph), len(graph[0]) # 행, 열 dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(r, c): queue = deque() queue.append([r, c]) cnt = int(graph[r][c]) while queue: x, y = queue.popleft() for i in range(4): nx, ny = x + dx[i], y + dy[i] if nx in range(n) and ny in range(m): # 범위 확인 if not visited[nx][ny] a..
전공/프로그래머스 2023. 10. 6. 21:47
전력망을 둘로 나누기

날짜 : 2023. 10. 01 사용 언어 : python 문제 코드 from collections import deque def solution(n, wires): def bfs(idx): queue = deque() queue.append(1) visited = [False] * (n + 1) visited[1] = True cnt = 0 while queue: now = queue.popleft() cnt += 1 for i in range(len(wires)): if i == idx: continue # 사용 불가능한 와이어 if now in wires[i]: # 방문 x, 경로에 있는 경우 if now == wires[i][0] and not visited[wires[i][1]]: visited..
전공/프로그래머스 2023. 10. 1. 21:38
15666

날짜 : 2023. 09. 30 사용 언어 : python 문제 코드 import sys def bt(idx, path): if len(path) == m: if path not in res: res.append(path) return for i in range(idx, n): bt(i, path + [a[i]]) return n, m = map(int, sys.stdin.readline().split()) a = list(map(int, sys.stdin.readline().split())) a.sort() # print(a) res = list() bt(0, []) res.sort() for i in res: print(*i) 풀이 - 기본적인 백트래킹을 활용한 문제 - 조건에 따라 입력받은 후 해당..
전공/백준 2023. 9. 30. 19:36
여행경로

날짜 : 2023. 09. 29 사용 언어 : python 문제 코드 def solution(tickets): used = [False] * len(tickets) # 사용여부 res = list() def dfs(now, path): # print(now, path) if len(path) == len(tickets) + 1: res.append(path) return for i in range(len(tickets)): if not used[i] and tickets[i][0] == now: # 현재 체크하는 티켓 사용 x, 출발지가 동일 used[i] = True # 사용체크 dfs(tickets[i][1], path + [tickets[i][1]]) # 리스트간 더하기 used[i] = False..
전공/백준 2023. 9. 29. 23:20
게임 맵 최단거리

날짜 : 2023. 09. 28 사용 언어 : python 문제 코드 from collections import deque def solution(graph): n, m = len(graph), len(graph[0]) for i in range(n): for j in range(m): if graph[i][j] == 1: graph[i][j] = 0 else: graph[i][j] = 1 answer = 0 queue = deque() queue.append([0, 0]) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] while queue: x, y = queue.popleft() if x == (n-1) and y == (m-1): return graph[x][y] + 1 for..
전공/프로그래머스 2023. 9. 29. 00:38
1238

날짜 : 2023. 09. 24 사용 언어 : python 문제 코드 import sys import heapq n, m, x = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(n + 1)] for _ in range(m): start, end, cost = map(int, sys.stdin.readline().split()) graph[start].append([end, cost]) INF = int(1e9) res = list() def dijkstra(start, end): dist = [INF] * (n + 1) # start 기준으로 거리 dist[start] = 0 # 본인 제외 queue = list() heapq.hea..
전공/백준 2023. 9. 24. 12:22
이전 Prev 1 2 3 Next 다음