BFS3 BOJ 1520 - 내리막길 https://www.acmicpc.net/problem/1520 접근그래프 탐색에서 내리막길로만 건너가는 문제이다. 이 문제의 핵심은 어떻게 모든 경로의 수를 구하냐가 관건이다.기존 BFS, DFS를 사용 시, 모든 경로를 탐색해야 하므로 500x500인 이번 문제에서 시간초과가 발생한다. 이 문제의 핵심은 Y->X와 Z->X로 갈 때, X의 경로의 수는 Y+Z 임을 이용하면 된다.이를 메모이제이션을 통해 DP[movedX][movedY]가 0인 경우(탐색되지 않은 경우)에는 계속 앞으로 전진하고,DP[movedX][movedY]가 0이 아닌 경우(이미 탐색된 경우)에는 DP[X] += DP[movedX][movedY]를 수행하면 된다. 이대로 수행하게 되면 문제가 발생한다.이미 진행된 경로에 대해서 .. 2024. 8. 16. BOJ 2206 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1차 시도 부수는 경우와 부수지 않는 경우 총 두가지의 경로가 존재한다. 따라서, 이를 해결하기 위해 부수는 경우를 이차원 배열을 이용하여 저장하려고 시도하였다. broken[][] map[][] chk[][] 그러나 이에 대한 문제가 존재한다. 만약 벽을 하나도 부수지 않는 경우에 이를 이용하면, 도달하지 못한다는 결과가 도출된다. 이런 문제가 발생하는 이유는 벽을 부순.. 2024. 3. 5. [BOJ 1941] 소문난 칠공주 https://www.acmicpc.net/problem/1941 2차원 배열에서 연속된 것을 구한다는 점에서 bfs나 dfs로 구할 수 있을 것같다. 그러나 BFS와 DFS는 뻗어나가는 형식이기 때문에 이런 규칙이 적용되지 않는 경우는 찾기 힘들다. 그래서 이번 문제는 단순히 이차원 배열에서 인접한 것만 찾는 방법 대신 S가 Y보다 큰 조합을 뽑은 다음, 서로 인접해있는지 체크하는 방법을 사용해야한다. 따라서 이중 for문을 통해 이차원 탐색을 하는 대신, 일차원 배열에서 가능성있는지 탐구한다.예를 들어, 1번째 사람이 올 수 있는지 -> 2번째 사람이 올 수 있는지 -> ... -> 25번째 사람이 올 수 있는지이 과정에서 백트래킹을 이용해 여러 조합들을 뽑을 수 있다. 그렇기 때문에 아래와 같이 일.. 2023. 3. 28. 이전 1 다음
