티끌모아 태산

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 설명 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 핵심 아이디어 해당 문제는 BFS 알고리즘을 통해 한칸씩 방문 후 최종 좌표에 도달했을 때 카운트 수를 출력하면 된다. 즉, 이동한 칸의 개수를 저장해나가며 탐색하는 것이 중요! 이를 2차원 배열에 저장하며 진행 코드 구현 #include #include #define MAX 101 using namespace std; int N, M; // 미로 크기 int graph[MAX][MAX]; // 미로 표현용 2차원 배열 int ..

https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 핵심 아이디어 R x C 맵에 못가는 부분 T가 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것. 백트래킹은 한정 조건을 가진 문제를 해결하는 전략으로, 탐색을 줄일 수 있다. DFS는 모든 경우를 탐색하지만, 백트래킹+DFS는 불필요한 탐색을 하지 않음. 백트래킹은 BFS와 DFS와 모두 구현이 가능하지만, 조..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 핵심 아이디어 외부 공기와 접촉한 치즈만을 녹이기 위해서는 값이 0인 부분만 BFS를 적용 초기 전체 치즈의 개수를 구해서 시간 마다 녹은 치즈의 개수를 뺀다. BFS 알고리즘 - 시간 마다 녹은 치즈의 개수를 반환, 그리고 치즈를 한번에 제거한다. 치즈가 다 녹으면 시간과 직전 치즈 개수 반환 그렇지 않으면 시간 +1 구현 코드 ''' 외부 공기와 접촉한 치즈만을 녹이기 위해서는 값이 0인 부분에 대해서..

https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 핵심 아이디어 BFS 탐색알고리즘 좌표 0을 bfs로 돌리는 것이 아니라 상어를 각각 bfs를 적용해서 최대 안전거리를 구한다. 보통 4가지 방향을 고려하는데, 여기서는 8가지 방향을 고려! 구현코드 ''' 안전거리는 그 칸과 가장 거리가 가까운 아기 상어와의 가리 안전거리의 최댓값 구하기. 즉, 가장 가까운 상어이면서 거리가 최대인 안전거리 구하기 모든 0에 대해서 ..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 핵심 아이디어 조합 라이브러리 완전탐색 문제 풀이 과정 치킨 집과 집의 좌표를 담는 리스트 생성해서 담기 치킨 집 중에서 m개를 골라 m개의 치킨 집 각 좌표를 담은 조합 리스트를 candidates 변수에 담기 m개의 치킨집과 집 사이의 거리 합을 구하는 함수 정의 get_sum(cadidate) 치킨 거리의 최소합 출력, result = int(1e9) 활용 구현 코드 '..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 핵심 아이디어 DFS + 구현 문제 해결 방법 mode라는 리스트로 CCTV의 종류(1, 2, 3, 4, 5)에 따라 회전했을 때 바라보는 방향을 넣어줌 사무실의 정보를 입력받을 때, cctv의 종료 및 위치(i,j)를 cctv 리스트에 append DFS를 돌려서 해당 cctv의 종류의 각도로 감시를 실행한 후, cctv 갯수만큼 CCTV로 감시를 다 했을 때 사각지대의 최솟값을 갱신..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 핵심 아이디어 분할 정복 -> 재귀 또는 스택으로 구현. 분할 정복이란 큰 문제를 하위문제로 나눠 풀어 상위 문제를 푸는 개념 재귀함수 - 로직은 같은데 매개변수가 변하는 것. 여기서는 분할 할 때 범위만 줄어든다. n = n // 2 풀이 n = int(input()) graph = [] for _ in range(n): graph.append(list(map(int, input()..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 핵심 아이디어 먼저 0으로 초기화된 배열을 생성해준다. 그리고 직사각형이 포함된 영역에 대해 1을 더해준다. DSF 탐색 알고리즘 활용. (BFS로도 가능) setrecursionlimit(10**6) 재귀의 깊이를 늘려줘야함 import sys sys.setrecursionlimit(10**6) m, n, k = map(int, input().split()) # 처음에 그래프..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 핵심 아이디어 DFS 탐색 알고리즘을 통해 풀 수 있는 문제, BFS로도 가능. O(N) 시간 복잡도 X -> M과 매치, Y -> N과 매치되는것에 주의! 풀이 dfs는 기본적으로 스택자료구조를 기반으로 재귀함수를 통해 구현됩니다. dfs를 구현하는 방식은 여러가지가 있는데 그 중 두 가지 방식을통해 구현하였습니다. import sys sys.setrecursionlimit(10000) def dfs(x,y..