본문 바로가기

그래프 이론15

[백준/C,C++] 1520번: 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 해당 문제를 보고 DFS, BFS문제구나 생각을 했습니다. 관건은 동적계획법을 사용해 어떻게 연산 수를 줄이는 것인가인데 다른 고수분들의 풀이를 보고 참고해 풀었습니다. DP[y][x] = 현재 지점의 좌표가 y, x일 때, 끝지점에 도달할 수 있는 경로의 개수로 가정하고 이를 사용한다면 탐색의 횟수를 줄일 수 있습니다. 예제를 통해 적용해보겠습니다. 최초 출발 지점인 50에서 10으로 갈 수 있.. 2021. 7. 4.
[백준/C,C++] 2206번: 벽 부수고 이동하기 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 개인적으로 BFS 기초를 공부하며 가장 어려웠던 문제인데, 관건은 벽을 부수고 도달한 최소 거리, 벽을 부수지 않고 도달한 최소 거리 모두를 기록하는 것입니다. 해당 부분을 다른 분들의 아이디어를 보고 해결하였습니다. bool 변수를 3차원으로 두는 것인데, 마지막에 [y][x][2] 의 3차원 형태로 구현함으로써 벽을 부수고 도달한 최소 거리, 벽을 부수지 않고 도달한 최소 거리.. 2021. 5. 5.
[백준/C,C++] 1697번: 숨바꼭질 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 경우의 수가 1을 뺀다, 더한다, 2를 곱한다. 3가지입니다. 3가지의 경우를 BFS로 탐색하며 결괏값과 일치하는 경우 깊이를 출력해주면 됩니다. #include #include using namespace std; const int MAX = 100001; int n, k; queue q; int depth[MAX]; int move(int n, int way) { if (wa.. 2021. 5. 5.
[백준/C,C++] 7569번: 토마토 www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 7576번: 토마토 문제와 비슷한데 3차원으로 업그레이드된 문제입니다... 2021. 5. 5.

티스토리툴바