해킹왕 양선규

# 도치가 사방으로 가는 것과, 물이 도치의 방문목록에 영향을 받는 것(도치가 지나간 길 안가는것)은 결과에 영향을 미치지 않는다. import sys from collections import deque input = sys.stdin.readline R, C = map(int, input().split()) # 행, 열 forest = [list(input().strip()) for _ in range(R)] visited = [[-1] * C for _ in range(R)] # -1로 설정해두고 도치의 이동 과정을 입력할것이다 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] queue = deque() for x in range(R): for y in range(C): if f..

import sys sys.setrecursionlimit(10 ** 9) input = sys.stdin.readline # 이분 그래프 판별 DFS 함수 def DFS(graph, start, visited, group): visited[start] = group for i in graph[start]: if visited[i] == 0: # 방문 안 한 곳이라면 result = DFS(graph, i, visited, -group) if not result: return False # 하위에서 이분 그래프 아니라고 판단했다면 함수 종료 elif visited[i] == group: # 인접노드인데 그룹이 같을경우 이분그래프 아님 return False return True # 입력받은 갯수만큼 그래..

import heapq import sys input = sys.stdin.readline N, E = map(int, input().split()) # 노드, 간선 graph = [[] for _ in range(N + 1)] # 그래프 입력받기 for _ in range(E): a, b, c = map(int, input().split()) graph[a].append((c, b)) graph[b].append((c, a)) visited = [False] * (N + 1) # 방문체크 리스트 def prim(graph, start): # 그래프, 시작노드 입력받는다, 프림 알고리즘 사용 visited[start] = True # 시작노드 방문체크 distance = 0 # 거리(가중치)를 계산할 변..

import heapq import sys INF = int(1e9) input = sys.stdin.readline N = int(input()) board = [] for _ in range(N): # 미로 입력받기 board.append(list(map(int, input().strip()))) distroy = [[INF for _ in range(N)] for _ in range(N)] # 부순갯수 visited = [[False for _ in range(N)] for _ in range(N)] # 방문목록 def goingNogoing(x, y): # 갈지말지 정하는함수 if 0

from collections import deque import sys input = sys.stdin.readline M, N, H = map(int, input().split()) # 가로, 세로, 높이 5, 3, 2 box = [] for i in range(N * H): # 토마토 입력받기 box.append(list(map(int, input().split()))) visited = [[False] * M for _ in range(N * H)] # 방문목록 box와 똑같이 만들기 def goingNogoing(box, x, y, visited): # 익힐수있는지 고민하는함수 if 0

import heapq import sys INF = int(1e9) input = sys.stdin.readline N = int(input()) # 도시 개수 ( 노드 개수 ) E = int(input()) # 버스 개수 ( 간선 개수 ) graph = [[] for _ in range(N + 1)] for _ in range(E): a, b, c = map(int, input().split()) # 출발노드, 도착노드, 거리 입력받기 graph[a].append([c, b]) # (거리, 도착노드) start, end = map(int, input().split()) # 계산해야 할 출발지, 도착지 distance = [INF] * (N + 1) # 최단 경로 리스트 def dijkstra(star..

import heapq import sys INF = int(1e9) input = sys.stdin.readline N, E, K, start = map(int, input().split()) # 노드, 간선, 찾을거리, 출발노드 graph = [[] for _ in range(N + 1)] for _ in range(E): a, b = map(int, input().split()) # 출발노드, 도착노드 graph[a].append([1, b]) # 거리(1), 도착노드 distance = [INF] * (N + 1) def dijkstra(start): queue = [] heapq.heappush(queue, (0, start)) # 시작노드거리, 시작노드 큐에 삽입 distance[start] ..

다익스트라(dijkstra) 알고리즘(최단 경로 알고리즘) - 그래프에서 한 정점까지의 최단 경로를 구하는 알고리즘 - 이 과정에서 도착 정점 뿐만 아니라, 모든 다른 정점까지 최단 경로로 방문한다. - 최단 경로를 구하는 과정에서, “각 노드에 대한 현재까지의 최단 거리” 정보를 항상 저장하고 갱신한다. - 매번 가장 비용이 적은 노드를 선택하는 것을 반복하기 때문에 그리디 알고리즘으로 분류되기도 한다. - 방향/무방향 그래프인지는 상관없다. 다익스트라 알고리즘 동작과정 - 우선순위 큐 사용을 위해 파이썬 heapq를 사용한다. 최소 힙으로 동작하기 때문에 항상 최단 거리를 pop하게 된다. 1. 최단 거리 테이블을 전부 INF(무한)으로 초기화한다. ( 일반적으로는 INF = int(1e9) 이다.)..

from collections import deque import sys input = sys.stdin.readline N = int(input()) # 노드(부품) 개수 E = int(input()) # 간선 개수 indegree = [0 for _ in range(N + 1)] # 진입차수 담을 리스트 needs = [[0] * (N + 1) for _ in range(N + 1)] # 부품별 요구부품량 담을 리스트 graph = [[] for _ in range(N + 1)] # 연결정보 담을 리스트 for _ in range(E): leaf, root, money = map(int, input().split()) graph[root].append([leaf, money]) indegree[lea..

파이썬 코드에서 a = -7 b = 2 일 때, 1. int(a / b) -> -3 2. a // b -> -4 가 된다. 1번은 a를b로 나눈 후 정수 형태로 바꾸기 위해 소수점 부분을 미련없이 버린다. 반면 2번의 // 연산은 “내림”을 수행한다. -3.5에서 “내림”을 하면 -4가 된다. 만약 양수인 3.5였다면 3이 되었겠지만, 음수에서는 더 작은 수가 -4기 때문에 그렇다. 이것을 신경쓰며 코드를 짤 필요가 있어 보인다. DAG(Direct Acyclic Graph) - 사이클이 없는(비순환적) 방향 그래프 위상 정렬(topological sort) - 사이클이 없는 방향 그래프(DAG)에서 정점들을 순서대로 나열하는 알고리즘. “선후관계를 만족하는 정점의 순서”를 찾는다. - 순서가 정해져 있..