Beelog

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

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제는 위와 같으며, 아기 상어 문제는 BFS 를 활용하여 문제를 풀 수 있습니다. 1. 현재 상어의 위치에서 가장 가까이에 있는 먹을 수 있는 물고기가 있는지 확인합니다. (BFS 사용) 2. 먹을 수 있는 물고기가 없다면, 그대로 반복을 종료하고 지금까지 물고기를 먹기 위해 이동한 시간(time 변수 값)을 출력합니다. 3. 먹을 수 있는 물고기가 있다면, (1) 먹은 물고기 수를 하나 증가시키고 (..

www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제는 위와 같으며, 나이트가 한번씩 이동할 때마다 몇번째 이동인지와 해당 위치(x, y)를 배열 형태로 우선순위 큐에 저장한 뒤 저장된 위치가 도착 지점과 일치하는 경우 해당 위치까지 이동한 칸의 수(몇번째 이동인지)를 출력하여 문제를 해결할 수 있습니다. 파이썬 코드는 다음과 같습니다. from sys import stdin import heapq # 나이트가 이동할 수 있는 위치 저장 dx = [-2, -2..

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제는 위와 같으며, 우선순위 큐와 BFS 를 통해 문제를 해결할 수 있습니다. 먼저 주어진 미로를 이차원 배열에 저장하고, 출발점(0,0)을 우선순위 큐에 추가합니다. 이때 [현재 위치까지 지나온 위치 수(현재 위치 포함), 현재 위치의 x 값, 현재 위치의 y 값] 형태로 데이터를 저장합니다. 현재 위치까지 지나온 위치 수를 기준으로 우선순위 큐에 데이터를 저장하게 되면 같은 위치를 확인하게 되는 경우 해당 위치까지 방문한 최소 위치 수를..