dfs5 [백준]BOJ 12100: 2048 (Easy) - Swift/DFS https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 위 링크 참조 (길어서 생략) 풀이 최대 20 * 20 크기의 보드에서 2048 게임을 하는 것이다. 최대 5번의 이동만 한다고 문제에 주어져 있으므로, 모든 경우를 탐색하여 문제를 풀 수 있다. 이 문제에서 주의해야할 점은 다음과 같다. 1. 이동하는 방향에서 가까운 숫자부터 이동해야한다. -> 당연하지만 먼 숫자부터 이동한다면 앞에 있는 숫자들 때문에 이동이 .. 2024. 4. 14. [백준]BOJ 1520 - 내리막 길 - Swift/DP & DFS https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 풀이 dfs를 이용하면 쉽게 풀 수 있는 문제일 것 같지만, 주어지는 그래프의 크기가 커서 시간초과가 나오는 문제이다. 하지만 이러한 문제들은 중첩되는 연산이 많으므로 DP를 이용하면 시간초과 없이 해결할 수 있는 경우가 흔하다. DP의 컨셉은 다음과 같다. 1. 그래프의 특정 칸에서 목적지로 도착하는 경우의 수는 앞선 경로에 상관없이 항상 같다. 2. 따라서 각 칸에서 목적지로 가는 경로의 수를.. 2023. 7. 6. [백준]BOJ 14502 - 연구소 - Swift/BFS & DFS https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 dfs와 bfs가 합쳐진 문제이다. 벽을 꼭 3개를 세워야 하므로 dfs를 이용하여 벽을 세울 위치를 전체 탐색할 수 있다. 연구소의 크기가 최대 8 * 8 이므로 전체 탐색하는데 큰 문제가 발생하지 않는다. 벽을 세웠으면 bfs를 이용하여 바이러스가 퍼졌을 때의 연구소의 모습을 그린다. 이 때 바이러스가 지나간 자리는 2로 마킹되고, 벽은 바이러스가 지나가지 못하므로 isVisited와 같은 배열.. 2023. 7. 5. [백준]BOJ 10451 - 순열 사이클 - Python https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 순열이 각각의 (1부터 시작하는)인덱스와 매칭되어있는 그래프를 만들면 쉽게 해결된다. (친절하게 문제에 그림도 있다.) 순열과 인덱스는 내부 원소들이 순서를 제외하고 같으므로 무조건 내부에 사이클을 형성하게 된다. 따라서 문제에서 주어진 그대로 우리는 서로 가르키는 방향을 재귀로 따라가고, 이미 방문한 숫자가 나온다면 재귀를.. 2022. 11. 6. [백준]BOJ 1260 - DFS와 BFS - Python/BFS, DFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 심플하다. 입력값으로 그래프가 주어지고, 우리는 DFS와 BFS를 이용해 탐색한 결과를 각각 출력하면 된다. from collections import deque def dfs(v, dfsArray): isVisitedDFS[v] = True dfsArray.append(v) for i in range(len(graph[v])): if graph[v][i] !.. 2022. 11. 6. 이전 1 다음
