https://www.acmicpc.net/problem/13913from collections import dequedef bfs(n, k): MAX = 100000 arr = [-1] * (MAX + 1) # 최단 거리(시간) 저장 prev = [-1] * (MAX + 1) # 이전 위치를 저장하는 배열 (경로 역추적) q = deque() q.append(n) arr[n] = 0 # 시작점 방문 while q: v = q.popleft() if v == k: # 목표 지점 도달하면 종료 path = [] while v != -1: path.append(v) ..

https://www.acmicpc.net/problem/13549from collections import dequedef bfs(n, k): q = deque([n]) arr = [-1] * 100001 # 방문 여부 및 걸린 시간 저장 (-1: 미방문) arr[n] = 0 # 시작점은 0초 while q: v = q.popleft() if v == k: # 동생 위치에 도달하면 시간 반환 return arr[v] # 순간이동 (우선적으로 처리, 가중치 0) if 0 여기서 *2 를 +1, -1보다 뒤에 배치하면 틀린다...🛑 순간이동을 큐 앞에 넣어야 하는 이유✅ popleft()는 큐의 앞에서 데이터..

https://www.acmicpc.net/problem/9466처음의 시간초과 풀이import sysinput = sys.stdin.readlinet = int(input())for _ in range(t): n = int(input()) # 학생 수 students = list(map(int,input().split())) # 선택한 학생들의 번호(학생 인덱스는 1부터 시작) students = [s - 1 for s in students] ans = 0 # 프로젝트 팀에 속하지 못한 학생들의 수 def dfs(start): global lst nxt = students[start] if nxt == start: st..

https://www.acmicpc.net/problem/5427불! 이랑 똑같은 풀이 (상근이 먼저 이동 -> 불 이동)import sysfrom collections import dequeinput = sys.stdin.readlinet = int(input())for tc in range(t): w, h = map(int,input().split()) arr = [list(input().rstrip()) for _ in range(h)] q = deque() ans = 'IMPOSSIBLE' # 상근이 먼저 이동 for i in range(h): for j in range(w): if arr[i][j] == '@': ..

https://www.acmicpc.net/problem/10026import sysfrom collections import dequeinput = sys.stdin.readlinesys.setrecursionlimit(10**6)n = int(input())arr = [list(input().rstrip()) for _ in range(n)]# 적록색약: R = G# 정상: R, G, Bnot_blind, blind = 0,0visited = [[0]*n for _ in range(n)]b_visited = [[0]*n for _ in range(n)]# 정상def dfs(i,j, color): for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: ..

https://www.acmicpc.net/problem/10971import sysinput = sys.stdin.readlinen = int(input())link = [list(map(int, input().split())) for _ in range(n)]visited = [False] * nmin_cost = float('inf')def dfs(start, current, count, cost): global min_cost # 모든 도시를 방문하고 시작점으로 돌아왔을 때 if count == n and link[current][start] > 0: min_cost = min(min_cost, cost + link[current][start]) retur..