[Gold I] 멀티탭 스케줄링 - 1700 문제 링크 성능 요약 메모리: 34120 KB, 시간: 68 ms 분류 그리디 알고리즘 문제 설명 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면, 키보드 헤어드라이..

N = int(input()) M = int(input()) import sys input = sys.stdin.readline print = sys.stdout.write result = 0 #a, b, cost edges = [list(map(int, input().split())) for _ in range(M)] edges.sort(key=lambda x: x[2]) parent = [i for i in range(N+1)] def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(a, b): a = find(a) b = find(b) if a > b: parent[a] = b else: parent..

from collections import deque def bfs(x, y): q = deque() q.append([x, y]) dx, dy = [1, -1, 0, 0], [0, 0, 1, -1] while q: cx, cy = q.popleft() for i in range(4): nx, ny = cx + dx[i], cy + dy[i] if 0

[백준] 안전 영역 (2468) - BFS 문제 링크: https://www.acmicpc.net/problem/2468 문제 요약 N x N 크기의 지역이 있다. 각 지역의 높이는 1 이상 100 이하의 자연수이다. 비가 내리면 높이가 같거나 낮은 지역은 물에 잠긴다. 물에 잠기지 않는 안전한 영역의 개수를 구하라. [위 문제 요약은 chat-gpt를 이용하였습니다.] import copy from collections import deque n = int(input()) graph = [list(map(int, input().split())) for _ in range(n)] max_height = max(map(max, graph)) def run(graph, visited, i, j): visit..

2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 아이디어에 대한 힌트는 인터넷을 참고하였다. 처음 풀어보는 유형이다. 아래 문제는 BFS를 2번 적용하여 탐색하였다. 우선 "섬" 인 곳은 라벨링을 하였고 (2~n) 여기서 섬을 찾을때 첫번쨰 BFS를 이용하였다. 두번쨰로 섬과 섬을 잇는 바다를 탐색할 때인데, BFS로 탐색 후 새로운 섬을 만나게 되면 이전의 result값과 비교한다. result와 비교하여 더 작은 값을 result에 넣은 후 마지막에 result를 출력하면 가장 짧은 다리의 거리가 나온다. 사실..

from collections import deque s, t = map(int, input().split()) MAX = 10e9 def BFS(): visited = set() q = deque() q.append((s, '')) operator = ['*', '+', '/'] result = -1 if s == t: return 0 while q: node, op = q.popleft() if node == t: result = op break for o in operator: calc = eval(str(node) + o + str(node)) if 0