BFS

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