Beelog

www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제는 위와 같으며, 이 문제는 시간당 물이 이동하는 경우와 고슴도치가 이동하는 경우를 나누어 BFS 방식을 통해 고슴도치가 비버 굴로 이동하는 최소 시간을 구하면 되는 문제입니다. 1. 숲의 정보를 이차원 배열에 저장하고, 이때 고슴도치의 출발 위치와 물의 위치(여러 개일 수 있으므로 배열에 저장)를 각각 저장합니다. 2. BFS 메소드를 수행하여 고슴도치가 안전하게 비버 굴에 도착할 수 있는 시간을 구합니다. (도착할 ..

www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제는 위와 같으며, 주어지는 층수 정보를 각각 변수에 저장한 뒤 시작 위치부터 위, 아래로 이동하는 경우를 확인하며 BFS 방식을 통해 문제를 해결할 수 있습니다. 파이썬 코드는 다음과 같습니다. from sys import stdin import heapq # 처음 위치부터 위, 아래로 이동하여 도착 위치에 도달할 때까지 누른 버튼 수 반환 def bfs(start): queue = [] heapq.heappush(qu..

www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 문제는 위와 같으며 BFS 를 통해 문제를 해결할 수 있습니다. 1. 먼저 정육면체 단위로 공간 정보가 주어지므로 3차원 배열을 사용하여 건물 내 칸 정보 (#, ., S, E) 를 저장합니다. 2. 건물 내 정보를 저장할 때 S, E 의 위치는 따로 저장합니다. 3. 시작 위치 S를 BFS 함수에 넘겨 출구 위치 E 까지 이동하는데 걸리는 시간을 반환하도록 합니다. 4. 해당 시간이 0이 아닌 경우 탈출이 가능한 ..

www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 문제는 위와 같으며, 이 문제는 BFS 와 Deque 를 사용하여 해결하였습니다. 먼저 모든 땅에 대하여 시작 땅부터 가장 멀리 떨어져 있는 땅까지의 최단 거리를 구한 뒤, 그 값과 기존에 구한 가장 먼 두 섬 사이의 거리와 비교하여 더 먼 값을 출력하는 방식으로 문제를 해결할 수 있습니다. 가장 멀리 떨어져 있는 땅까지의 최단 거리는 deque 를 사용하는 BFS 방식으로 해결할 수 있습니다. 파이썬 코드는 다음..

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제는 위와 같으며, 새로운 3개의 벽을 세울 수 있는 모든 경우의 수를 확인하면서, 새로운 벽을 세웠을 때 바이러스가 퍼지는 것을 BFS 로 구한 뒤 전체 연구소 구역을 모두 확인하여 바이러스가 퍼지지 않은 구역의 수를 구해 기존 최대 안전 지역 수와 비교하여 더 큰수를 저장하였다가 최종적으로 출력하는 방식으로 문제를 해결하였습니다. 파이썬 코드는 다음과 같습니다. from sys import stdin from iter..