코딩딩/BOJ

https://www.acmicpc.net/problem/2638간만에 만족스러운 풀이가 나와서 포스팅import sysfrom collections import dequeinput = sys.stdin.readline'''바깥공기부터 탐색만약 공기에 노출된 치즈를 발견할시 해당 치즈의 값을 +1 만약 그렇게 더한 치즈의 숫자가 2 이상일경우 melting cheese에 추가순회가 끝나면 melting cheese에 담겨있던 치즈를 다 녹인다.melting cheese를 탐색 queue에 append여기서 포인트는 melting count를 계속 유지해주며 작업 queue에 더해주는것같음필요한 자료형치즈 graphmelting count graph작업 queuemelting queuevisited'..

import sysfrom collections import dequeinput = sys.stdin.readlinedy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]# 여기서 병합 가능한 국경을 추려서 그 좌표를 담은 2차원 list를 반환한다.def check(y, x, visited): # 단순 bfs로 인접한 국경중 병합이 가능한 국경을 추린다 check_list = [] queue = deque([(y, x)]) visited.add((y, x)) while queue: cur_y, cur_x = queue.popleft() for i in range(4): new_y, new_x = cur_y + dy[i],..

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