알고리즘

import sysfrom collections import dequeinput = sys.stdin.readlineINF = float('-inf')'''결국 bfs + 비트마스킹을 응용하면 되는 문제였음문제를 이해하기까진 어려웠지만 이해 후엔 그냥 무지성 bf랑 똑같았음'''def bfs(N, initialPositions): distance = [INF] * (N + 1) # BFS 큐 초기화 queue = deque() # 초기 위치 설정 for position in initialPositions: distance[position] = 0 queue.append(position) maxDistance = 0 while queue: ..

처음 접근은 무지성 BFS 두번 돌리는걸로 시도했다.당연히 플레 문제답게 결과는 시간초과... import sysfrom collections import dequeinput = sys.stdin.readlinedy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]'''빙산 + bfs로 생각하면 될듯 함모든 빙산의 위치 좌표를 set 자료형에 저장백조 한마리의 위치정보 담기day = 0while True: tmpIce = [] set 자료형을 순회하며 물과 접촉하는 빙산을 탐색 만약 접촉한다면 set에서 제외하고 tmpIce에 append tmpIce에 저장되어있는 ice를 모두 녹임 백조 bfs 순회 시작 day += 1 시간초과!!내 생각엔 지금..

import sysfrom collections import dequeinput = sys.stdin.readline'''지금 로직은 한눈에 봐도 문제가 많아보임visited 처리를 어떻게 해야할지가 관건내 가설만약 동생이 도착한곳에 이미 visited 처리가 되어있다면수빈이는 왓다리 갔다리 움직이며 해당 장소에 머물 수 있음여기서 또 문제 발생홀수와 짝수 레벨에 따라 엇갈리는 상황 발생!이를 해결하기 위해 visited를 홀, 짝으로 나눠주는게 필요할듯'''def bfs(n, k): visited = [[False] * 500001 for _ in range(2)] queue = [n] curTime = 1 k += curTime visited[0][n] = True w..

import sysfrom collections import dequefrom collections import defaultdictdy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]input = sys.stdin.readline'''약간 불켜기와 비슷한 문제인것같은가장자리의 모든 좌표를 queue에 집어넣어두고 시작소유하고 있는 key를 set 자료형에 집어넣기door는 key : (좌표), (좌표) 이런식으로 저장될것평상시처럼 탐색. 만약 문을 찾으면 가지고 있는 key가 해당 문을 열 수 있는지 확인 없으면 door에 좌표와 필요한 key를 저장 만약 key를 찾으면 key를 set 자료형에 집어넣기 소유중인 door중에 문..

import sysfrom collections import dequeinput = sys.stdin.readline'''벽부 2에다가 낮, 밤 하나만 추가하면 될듯'''dy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]def bfs(k): queue = deque([(k, 0, 0, 1, True)]) # k, y, x, time, is_day visited[0][0][k] = 1 while queue: curK, curY, curX, time, is_day = queue.popleft() if curY == n - 1 and curX == m - 1: print(time) sys.exit() ..

import mathimport sysimport heapqinput = sys.stdin.readlineINF = math.inf'''모든 경로가 가지고 있는 값을 최신화모든 경로의 경우의수를 계산해야함 (다익스트라)하지만 모든 노드의 간선을 graph화 하면 메모리 낭비 장난 아닐듯heapq 쓰면 해결'''dy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]def bfs(): # heapq 생성 (간선 가중치, 좌표) heap = [] heapq.heappush(heap, (graph[0][0], 0, 0)) while heap: curDist, curY, curX = heapq.heappop(heap) if curY == n - 1 and ..

import sysfrom collections import dequeinput = sys.stdin.readlinedef can_reach(start, end): return abs(start[0] - end[0]) + abs(start[1] - end[1]) 현재 위치 -> 페스티발 or 현재 위치 -> 편의점 -> 페스티발이런식으로 조회함

오답코드!import sysfrom collections import dequeinput = sys.stdin.readline'''벽 부수고 이동하기!graph를 3차원으로 접근하면 되지 않을까queue에 집어넣는 값을 (y, x, K, count) 이렇게 넣고 K가 0이 되거나 y, x가 유효하지 않은 범위에 들어가면 안넣기그렇게 가장 빨리 도착하게 되는 값의 count를 print'''dy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]def bfs(K): # y, x, count, K queue = deque([(K, 1, 0, 0)]) visited = {(0, 0, K)} while queue: curK, curCount, curY, curX = ..

import sysfrom collections import deque, defaultdictinput = sys.stdin.readline'''우선 bfs 탐색을 할거임하지만 여기서 while queue가 아닌 S의 숫자만큼 반복 -> index로 판별하면 될듯2중 queue를 사용하면 될것같음! + key값을 index로 둬도 좋을듯각 플레이어의 위치를 2차원 queue에 저장 ex) [{i : [(1, 2), (3, 4)]}, {i : [(5,5]}] 여기서 queue에 있는 queue를 하나 빼오고 이걸로 탐색 시작 while True가 아닌 for i in range(S[index]) 자잘한 조건 붙여서 확장 반복이 끝나면 queue의 최종 형태를 global..

import sysfrom collections import dequeinput = sys.stdin.readline'''평범한 BFS에서 약간의 응용이 들어감horse의 움직임과 monkey의 움직임을 저장함수에 들어가기 전 0으로 초기화된 그래프 생성visited, queue 초기화 여기서 queue에 들어갈 인자는 x,y 뿐만 아니라 말처럼 움직일 수 있는 횟수, 지금까지 움직인 횟수까지 curY, curX, horseCount, curMove = queue에 들어있는 값을 빼온다 만약 horseCount가 유효하면 > 0 horse 이동방식으로 graph에 족적 남기고 queue에 위치 더하기 - 함수로 빼놓으면 가독성 올라갈듯 horseCount -=..