방배동 고구마

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 백준 2468번, 안전영역에 대한 풀이이다. 문제는 링크를 참조해주기를 바란다. 문제해결 빗물의 높이가 주어지지 않는 상황에서 Input의 범위를 보고 빗물의 높이를 추정해야하는 것이 주의점이다. 영역의 탐색은 전체 map을 순회하며 visit되지 않은 구역을 Dfs로 탐색하며 방문 표시를 하기로 하였다. 인접 연결된 지역은 하나의 지역으로 판단되므로 Dfs 호출시에 cnt를 올려주었다. 필자는 탐색을 ..

순열은 조합과는 다르다. 순열은 순서가 중요시 되는 수열이다. 예를들어 5개의 숫자 중 3개를 순서에 상관없이 고르는 것은 조합이다. 즉, 조합에서 (1,2,3)과 (3,2,1)는 같은 경우로 판단된다. 그러나 순열은 다르다. 순서가 중요하기 때문에 순열에서 (1,2,3)과 (3,2,1)은 다르다. 중고등학교에서 배웠던 공식이 기억날 것이다. 사실 기억나지 않는다. 0!은 1이다. 기억을 더듬어 5개의 숫자중에 3가지를 뽑아내는 조합의 경우의 수는 10이며, 순열은 60가지가 되겠다. 이를 코드로 어떻게 구현할 수 있을까? 순열 보통의 경우 DFS 알고리즘으로 순열을 구현할 수 있다. 5가지의 수 중에 3가지를 뽑아내는 순열의 경우는 아래와 같다. void Dfs_permutation(int level)..

문제 주어지는 노드사이에는 최대 1개의 도로가 있으며 양방향 도로이다. 도로에는 가중치가 있으며 노드간 이동시에는 최단 경로로 이동한다. N, 노드 수 : 5~100 M, 도로 수 : 5~5000 D, 노드 사이의 거리 이때 각 노드를 출발점으로 할때 도착 노드까지의 거리가 가장 먼 거리를 X라고 하자. 노드 중의 X가 가장 작은 X의 값을 구하라 입력 N과 M이 입력되며 노드A와 노드 B 사이의 거리 D가 아래와 같이 입력된다. 5 7 1 2 5 3 2 14 2 4 5 1 3 10 4 3 15 5 4 15 3 5 8 출력 15 입력을 그래프로 표현하면 위와 같다. 접근방식 서로 다른 가중치가 있는 맵이므로 BFS로 접근이 유효하다. BFS는 크게 2가지 종류가 있는데, 가중치가 서로 다른 경우와 가중치..

문제 주어진 지도에서 1구역, 2구역이 주어진다. 1구역에서 2구역으로 상하좌우 한칸씩 이동할 수 있다. 1구역에서 2구역으로 갈 수 있는 최단 거리를 구하라. 입력 N은 행, M은 열이며 map이 0과 1로 구분되어 입력된다. 0은 이동경로이며 1은 구역을 의미한다. 6 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 출력 4 접근방법1 1. map 전체를 탐색하여 1구역을 DFS로 확산하며 좌표를 저장한다..

문제 N, R, P 각각의 인풋이 주어진다. N은 필름의 개수이고 R과 P는 필름의 특성값이다. R은 곱의 성능, P는 합의 성능이라고 할때 R과 P의 차이값이 최소인 경우가 가장 필름화면의 성능이 우수한 경우이다. 주어진 N개의 필름에서 최적의 성능을 위해 제거할 필름의 최대갯수를 구하라 입력 4 2 10 2 8 3 4 4 12 출력 1 문제해결 모든 경우의 수를 조합하는 것이다. 모든 경우의 수는 조합이며 조합은 즉, DFS로 접근 가능하다. DFS를 조합으로 나타낼때 다중트리나 이중트리로 접근한다. 다중트리는 노드를 중심으로, 이중트리는 노드의 방문 혹은 선택여부를 중심으로 판단한다. ※ 재귀함수 추적시 확인점 0. 함수 Call되어 Stack caller에 쌓인 경로 1. Code에 의해 Retu..

문제 N*N 크기의 map이 있음 Input으로 map 크기에 맞는 cost가 들어옴 (0,0) 부터 (N-1,N-1) 까지 가는 최소비용을 구하라 입력 N은 2이상 100이하의 자연수이다. 3 041 253 620 Output 8 문제해결 더보기 DFS는 모든 경우의 수이다. 시간복잡도가 오래걸릴 수 있다.BFS를 이용하여 최소의 경우를 구할 수 있다. 단 중복방문을 무조건 허용하지 않고 이전 비용보다 좋을때 허용할 수 있도록 한다. DFS로 최초 풀이해보았으나 N이 커지면 Timeout이 났다. 모든 경우의 수이기때문에 시간복잡도가 매우 높을 것이다. #include int N; char map[100+10][100+10]; int visit[100+10][100+10]; int dx[4] = {1,..