백준2 [DP, DFS] 백준 1520 내리막길 C++ https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 : 일반적인 DFS로 풀었다가 시간초과나서 한참을 고민한 문제.. 결국 인터넷에서 풀이를 찾아봤는데 핵심은 DP를 쓰는 것이다 백트래킹인가 해서 삽질을 몇시간 했는데 결국 풀지 못함.. 결국 DP배열로 경로를 저장해두면 쉽게 풀린다. 경로를 저장한다는 개념이 좀 추상적인데 결국 map[0][0] 에서 map[m-1][n-1] 까지 가는 경로의 수를 구하는 문제 이므로 dp[i][j] 란 (i, j.. 2021. 8. 24. [DFS,BFS] 백준 2583 영역구하기 C++ https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 : 풀이 : bfs 문제 중에 그림(백준 1926) 문제와 유사해서 그걸 풀었던 방식과 비슷하게 풀었다. 좌표의 최대값(100)크기의 이차원 배열을 만들어서 색칠된 부분을 1 색칠이 안된 부분을 0으로 두고 bfs 탐색을 통해 0인 부분의 넓이를 구하는 방법이다. 이런 식으로 구해진 넓이는 우선순위 큐에 넣어서 오름차순으로 정렬하여 출력가능 단, 조금 주의해야 할 점이 있.. 2021. 8. 16. 이전 1 다음
