Python

문제https://www.acmicpc.net/problem/5014 아이디어 현재 위치 s에서 목표 위치 g까지 도달해야 하며, 한 번에 위로 u층 혹은 아래로 d층 이동 가능BFS를 사용하여 최소 버튼 클릭 횟수를 구함방문 배열로 중복 탐색을 방지하고, floor 배열에 버튼 클릭 횟수를 기록 CODEimport sysfrom collections import dequeinput = sys.stdin.readlinef, s, g, u, d = map(int, input().split())floor = [0] * (f+1)visited = [False] * (f+1)dx = [u, -d]def bfs(x): queue = deque() queue.append(x) # 시작점 S층 ..

문제https://www.acmicpc.net/problem/4179 아이디어 불의 전파 시간과 지훈의 이동 시간을 별도의 BFS로 나눠서 계산해당 칸에 불이 도착하는 시간 > 지훈이 도착하는 시간일 때만 이동불은 다중 시작점(모든 ‘F’)으로 큐에 먼저 넣고 확산 시간 채움지훈은 ‘J’에서 시작하여 테두리에 도달하는 순간의 시간을 정답으로 반환 CODE import sysfrom collections import dequeinput = sys.stdin.readliner, c = map(int, input().split())maze = [list(input().strip()) for _ in range(r)]# 거리 및 방문 배열 (불/지훈 분리)fire_dist = [[-1] * c for _ i..

문제https://www.acmicpc.net/problem/2667 아이디어 지도에서 1은 집이 있고, 0은 집이 없는 칸을 의미연결된 집들을 하나의 단지로 묶어 단지의 개수와 각 단지의 집 수를 구해야 함BFS 탐색을 이용하여, 집(1)이면서 방문하지 않은 칸을 시작점으로 단지를 확장BFS가 끝날 때마다 한 단지의 집 수를 반환 → 리스트에 저장최종적으로 리스트의 길이가 단지 개수이며, 리스트를 정렬하여 출력 CODEimport sysfrom collections import dequeinput = sys.stdin.readlinedx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]def bfs(x, y): queue = deque() queue.append((x, y)..

문제https://www.acmicpc.net/problem/2583 아이디어 주어진 입력은 직사각형의 좌표인데, 이를 점이 아니라 격자의 칸 단위로 해석해야 함직사각형으로 채워진 부분은 탐색할 수 없는 영역이므로, 2차원 배열에 1로 표시하여 벽으로 처리탐색 가능한 칸(0)을 기준으로 BFS를 실행하여 연결된 영역의 넓이를 구함BFS 수행 중 칸을 하나 방문할 때마다 넓이를 +1 해주면 해당 영역의 크기를 계산 가능모든 좌표를 돌면서 BFS를 수행해 영역의 개수와 각 영역의 넓이를 리스트로 저장 CODEimport sysfrom collections import dequeinput = sys.stdin.readlinedef bfs(x, y): queue = deque() queue.ap..

문제https://www.acmicpc.net/problem/2573 아이디어 매년 빙산은 인접한 바다(0)의 개수만큼 높이가 줄어듦빙산이 두 덩어리 이상으로 나눠지는 시점을 구해야 함핵심 아이디어는 빙산 탐색과 동시에 해빙 계산을 처리하는 것melt_num 배열을 만들어 각 칸이 인접한 바다의 개수를 기록BFS 탐색 중에 인접 바다 수를 세어 melt_num에 반영하고, 동시에 빙산 덩어리 개수를 파악 CODEimport sysfrom collections import dequeinput = sys.stdin.readlinen, m = map(int, input().split())graph = []for _ in range(n): graph.append(list(map(int, input..