Beelog

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/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제는 위와 같으며, 지도의 정보를 이차원 배열로 저장하고 각 섬을 방문한 적이 있는지 확인하는 이차원 배열을 만든 후, 기본적인 DFS 를 통해 연결된 땅을 모두 방문처리하고 나서 섬의 개수를 증가시키는 방식으로 섬이 몇개인지 확인할 수 있습니다. 파이썬 코드는 다음과 같습니다. import sys sys.setrecursionlimit(10000) # 재귀함수 범위 제한 수정 # 상하좌우, 대각선까지 ..

www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제는 위와 같으며 이 경우는 일반적인 DFS 를 통해 연결 요소를 확인하고 그 수를 세면 해결할 수 있는 문제입니다. 파이썬 코드는 다음과 같습니다. from sys import stdin # 일반적인 DFS 수행 (연결 요소 찾기) def dfs(start): queue = [start] while queue: node = queue.pop() ..

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