본문 바로가기

분류 전체보기

(402)
[백준 2638번] 치즈 (Python3) import sys input = sys.stdin.readline from collections import deque N,M = map(int,input().split()) dy = [1,-1,0,0] dx = [0,0,1,-1] cheese = [] for i in range(N): cheese.append(list(map(int,input().split()))) def melt(n): dq = deque() dq.append((0,0)) melted = False while dq: y,x = dq.popleft() if cheese[y][x] == n: continue elif cheese[y][x] == -n: cheese[y][x] = n melted = True continue elif ch..
[백준 2206번] 벽 부수고 이동하기 (Python3) 많은 시행착오가 있었던 문제다. 가장 처음에 내가 생각한 방법은 "그냥 BFS 때리면서 벽을 지났는지 안지났는지 세고, 한번도 안지났으면 지나자" 였는데 틀렸다. 어디서 틀렸을까 고민해보다 나온 결론은 한번 벽을 뚫고 간 쪽에서 그 다음벽 주변을 먼저 탐색해버려서 벽을 한번도 안뚫으면 그 주변에 아예 접근도 못한다는 거였다. 그래서 생각한 다음 방법은 모든 벽을 기준으로 벽에서부터 BFS를 해서 시작점과 끝점까지 얼마나 걸리는지 측정하고, 그 합이 가장 작은값을 취하는 거였는데, 당연하게도 시간초과가 났다. 벽이 100개면 BFS를 100번, 1000개면 1000번 돌려야하니 당연한 결과... 마지막으로 생각한 방법은 0,0에서 BFS한번, 도착점에서 BFS 한번 하고 모든 벽의 4방향 주변을 체크하여 ..
[백준 1865번] 웜홀 (Python3) import sys input = sys.stdin.readline INF = 2000000000 def BF(start): bf = [INF]*(N+1) bf[start] = 0 for i in range(N): for x1,x2,t in graph: if bf[x2] > bf[x1]+t: bf[x2] = bf[x1]+t if i == N-1: return True return False T = int(input()) for test in range(T): N,M,W = map(int,input().split()) graph = [] for i in range(M): x1,x2,t = map(int,input().split()) graph.append((x1,x2,t)) graph.append((x2,..
[백준 1238번] 파티 (Python3) import sys input = sys.stdin.readline from collections import deque import heapq INF = sys.maxsize N,M,X = map(int,input().split()) graph = [[] for i in range(N+1)] dij = [[INF]*(N+1) for i in range(N+1)] for i in range(M): x1,x2,t = map(int,input().split()) graph[x1].append((x2,t)) def Dijkstra(start): hq = [] heapq.heappush(hq,(0,start)) while hq: w,now = heapq.heappop(hq) if dij[start][now]
[백준 17144번] 미세먼지 안녕! (Python3) import sys input = sys.stdin.readline from collections import deque import copy dy = [1,-1,0,0] dx = [0,0,1,-1] N,M,T = map(int,input().split()) room = [] for i in range(N): room.append(list(map(int,input().split()))) def spread(): dq = deque() for i in range(N): for j in range(M): if room[i][j]==-1 or room[i][j]==0: continue s = room[i][j]//5 count = 0 for k in range(4): y = i+dy[k] x = j+dx[k]..
[백준 14938번] 서강그라운드 (Python3) import sys input = sys.stdin.readline from collections import deque INF = sys.maxsize N,M,R = map(int,input().split()) item = deque(map(int,input().split())) item.appendleft(0) graph = [[INF]*(N+1) for i in range(N+1)] for i in range(R): x1,x2,r = map(int,input().split()) graph[x1][x2] = graph[x2][x1] = r for k in range(1,N+1): for i in range(1,N+1): for j in range(1,N+1): if i == j: graph[i][i]..
[백준 12851번] 연구소 (Python3) import sys input = sys.stdin.readline from collections import deque from itertools import combinations import copy N,M = map(int,input().split()) roomorg = [] for i in range(N): roomorg.append(list(map(int,input().split()))) dy = [1,-1,0,0] dx = [0,0,1,-1] dq = deque() def virus(): dq = deque() for i in range(N): for j in range(M): if room[i][j] == 2: dq.append((i,j)) room[i][j] = 0 while dq: y,..
[백준 11404번] 플로이드 (Python3) import sys input = sys.stdin.readline from collections import deque import heapq INF = sys.maxsize N = int(input()) M = int(input()) bus = [[INF]*(N+1) for i in range(N+1)] dij = [[INF]*(N+1) for i in range(N+1)] for i in range(M): x1,x2,w = map(int,input().split()) if bus[x1][x2] > w: bus[x1][x2] = w def Dijkstra(start): hq = [] heapq.heappush(hq,(0,start)) while hq: w,now = heapq.heappop(hq) i..