본문 바로가기

DFS4

[백준/C++] 1405. 미친 로봇 문제 https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 로봇이 4방향 (동서남북)으로 각각 이동할 확률과, 이동 횟수가 주어질 때 로봇이 한 번 방문한 곳을 다시 방문 하지 않을 확률을 구하는 문제이다. 풀이 가능한 모든 이동 경로를 탐색하면서 이전에 방문했던 칸을 다시 방문하지 않은 이동경로의 확률을 구해서 모두 더하면 된다. DFS로 풀었다고 생각했는데, 백트래킹이라고 한다..? 내가 이해하기로는 N번 이동하는 걸 탐색한다고 할 때 매번 .. 2021. 8. 17.

[백준/C++] 1967. 트리의 지름 문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 처음에 문제를 봤을 때, 어떤 알고리즘을 이용해야 하는지 감이 오지 않았다. 그래서 검색을 좀 해보았는데, 공식처럼 트리의 지름을 구하는 알고리즘이 존재했고, 해당 알고리즘을 증명해놓은 글들도 많았다. https://blog.myungwoo.kr/112 (참고한 블로그) [트리의 지름 알고리즘] 1. 임의의 정점 x를 잡는다. (보통 루트로 잡음) 2. x에서 가장 .. 2021. 6. 29.

[백준/C++] 1987. 알파벳 문제 www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해.. 2021. 5. 4.

[백준/C++] 1520. 내리막 길 문제 www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 처음에는 DP만 이용해서, cache[i][j]에 (i,j) 위치까지 도착할 수 있는 모든 내리막길 경우의 수를 저장하려고 했다. 하지만, 상하좌우로 모두 이동이 가능했기 때문에 이 방법은 실패했다. 두 번째 생각난 방법은, 최단경로찾기 문제로 해석해서 BFS로 푸는 방법이었다. 하지만, 시간초과 때문에 이 방법은 실패했다. 최종 방법은, DFS에 DP를 접목한 방법이다. DFS로 탐색하되, DP의 메모리.. 2021. 3. 14.

이전 1 다음

티스토리툴바