전체 글

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 syssys.setrecursionlimit(10**6)input = sys.stdin.readlinedef dfs(cur, cost): global visited currentLocation = graph[cur] currentType = currentLocation[0] nextLocation = list(map(int, currentLocation[2:-1])) if currentType == "L": cost = max(cost, int(currentLocation[1])) elif currentType == "T": cost -= int(currentLocation[1]) if cost  재귀도 다시 익혀야겠다  ..

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 defaultdict, dequeinput = sys.stdin.readlinedy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]'''베시시visited를 처리하는 graph와 불의 현황을 저장하는 graph 두개가 필요함.우선 visited에 방문을 표시하고 만약 불이 켜져있다면 queue.append필요한 자료구조.현재 탐색을 진행할 queue.방문 처리와 불이 켜진 위치를 저장할 graph 2개스위치의 위치와 어떤 방 불을 킬 수 있을지 저장할 dict 하나이렇게 bfs'''def bfs(): queue = deque([(1, 1)]) visited[1][1] = True turnOn[1][1] = True ..

길고 길었던 5개월이 벌써 다 지나가버렸다. 매일같이 회고를 적어야지 적어야지 하고 미루다 수료식을 마친 이제야 정말 끝났다는 실감이 나 이렇게 회고를 남겨본다, 정들었던 경기대학교 캠퍼스를 떠나기 전 내가 왜 크래프톤 정글에 뛰어들었는지, 내가 얻어간것과 잃은것은 무엇이 있는지 한번 정리해보려고 한다. 크래프톤 정글에 들어가야겠다고 다짐한 계기는 다음과 같다. 단순 Framework 만 다룰 줄 안다고 지속 가능한 개발자가 될 수 있는걸까?? 국비 지원 교육을 한차례 받고 Java Spring을 겨우 다룰 줄 알게 된 나는 이런 고민에서 벗어날 수 가 없었다. 자료구조와 각종 알고리즘, 그리고 컴퓨터의 기본 작동 방식도 아무것도 모르는 내가 고작 Spring boot 하나 다룰 줄 안다고 정말 좋은 개..

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 -=..

애기 상어 뚜루뚜뚜루 import sysfrom collections import dequeinput = sys.stdin.readlinedy = [-1, 0, 1, 0]dx = [0, -1, 0, 1]# 풀이'''물고기의 위치를 set 자료형에 담아둬야 한다.1. 아기상어 뚜루뚜루루 set 자료형으로 visited 유무 판별 (초기화에 유리)2. 아기상어 기준 위, 왼 (search 함수 만들기) a. 상 좌 하 우? 순서로 탐색하기 (조건에 맞으면 bfs 탐색) 만약 물고기를 먹었다면 탐색 종료 (visited 자료형 초기화, 상어 위치 재정의), 거기다 지금 상어가 물고기 몇마리 먹었는지 판별해서 크기 키우기3. 만약 상어가 다먹었는데 남아있는 물고기가 남아있다면 엄..