dfs2 백준 17090 미로 탈출하기 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net 1번 예제를 살펴보면 모든 영역에서 D이므로 아래로 내려가면서 경계선 밖으로 이탈합니다. 따라서 모두 미로 탈출이 가능하므로 정답은 9가 됩니다. 풀이. 시간을 단축하기 위해 DP 알고리즘과 DFS알고리즘을 적절히 사용해줍니다. DFS알고리즘을 사용하여 탐색한 경우 이미 도달한 적이 있었던 칸은 이미 결과가 정해 져 있기 때문에 다시 한번 탐색할 필요가 없습니다. dp 배열을 칸수만큼 만들어주고 기본값으로 -1을 할당해 주었습니다. -1의 경우 방.. 2022. 5. 27. 백준 2668 숫자고르기 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 간단히 예제를 살펴보면 싸이클이 발생한 구간 1, 3, 5를 순서대로 출력하면 됩니다. 즉. 무한 싸이클이 발생하는 구간의 정수들을 모두 순서대로 출력해주면 됩니다. 1. 깊이 우선 탐색(DFS) 알고리즘을 이용해 싸이클이 발생하는지 확인합니다. 2. 싸이클이 발생하였다면, 그 때 방문했던 모든 노드들은 정답이 되기때문에 'check'배열에 따로 저장해주겠습니다. 3. 위와 같이 N개의 노드를 탐색하면 되는데, 이전에 싸이클이 발생했던 구간(chec.. 2022. 5. 27. 이전 1 다음
