Algorithm study6 [백준 1260 / Python(파이썬)] DFS와 BFS 문제 풀이 DFS의 경우 재귀 함수를 이용하여 그래프를 탐색한다. BFS의 경우 queue를 이용하여 그래프를 탐색한다. # BOJ1260_DFS와BFS from collections import deque n, m, v = map(int, input().split()) graph = [[] for _ in range(n+1)] visited = [False for _ in range(n+1)] for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) for i in range(len(graph)): graph[i].sort() def dfs(graph, start): global dfs_answer,.. 2022. 10. 4. [백준 1197 / Python(파이썬)] 최소 스패닝 트리 [백준 1197 / Python(파이썬)] 최소 스패닝 트리 문제 풀이 크루스컬 알고리즘(Kruskal Algorithm) 이용 알고리즘을 이용하여 가중치의 크기를 구한 뒤 print해준다. 틀린 풀이: 시간 초과 #최소 스패닝 트리 import sys V, E = map(int, sys.stdin.readline().split()) arr = [list(map(int, sys.stdin.readline().split())) for _ in range(E)] arr.sort(key=lambda x: x[2]) uf = [i for i in range(V+1)] #union-find def kruskal(): global V, E, arr, uf mst = 0 #최소 스패닝 트리의 가중치를 담음 for u.. 2022. 7. 29. [백준 1700 / 파이썬(Python)] 멀티탭 스케줄링 [백준 1700 / 파이썬(Python)] 멀티탭 스케줄링 문제 풀이 이 문제는 그리드 알고리즘이므로 문제를 풀기 위한 기준을 나누어줬다. 1. 멀티탭에 이미 전기용품이 꽂혀있을 때: continue 2. 멀티탭에 구멍이 남아있을 때: 전기용품을 꽂아주고 continue 3. 멀티탭에 구멍이 없어 전기용품을 바꿔줘야할 때: 3-1 남은 순서 중에 계속 써야하는 전기용품이 없을 때: 멀티탭에서 뺄 전기용품의 위치를 바꾸어준 뒤 break 3-2 계속 전기용품을 써야할 때: 이후 순서에서 써야하는 전기용품 중 가장 멀리있는 것으로 위치를 바꾸고, 멀티탭에서 뺄 전기용품의 위치를 바꾸어준다. 틀린 풀이 idx와 farN의 초기화가 진행되지 않아 27%에서 틀렸다. n, k = map(int, input().s.. 2022. 7. 28. [백준 14179/파이썬(Python)] 빗물 [백준 14179/파이썬(Python)] 빗물 문제 풀이 2차원 세계에서 빈공간과 벽을 0과 1로 나누어줌 2차원 세계의 가장 바닥부터 왼쪽에서 오른쪽으로 벽인지 아닌지 검사 temp라는 배열을 만들어준 뒤 왼쪽 벽과 오른쪽 벽에 대한 가로 좌표를 저장 temp의 길이가 총 2가 되면(왼쪽 벽이 나타난 뒤 오른쪽 벽이 나타나면) 벽이 붙어있는지 검사 붙어있지 않으면 빗물이 고이는 부분을 0에서 2로 수정하고 빗물의 양을 count 해줌 # 빗물 h, w = map(int, input().split()) arr = list(map(int, input().split())) m = [[1] * w for _ in range(h)] temp = [] #왼쪽의 벽 가로 좌표와 오른쪽에 존재하는 벽 가로 좌표 저장.. 2022. 7. 18. 이전 1 2 다음
