728x90 반응형 백준 알고리즘/그래프2 [백준 2665][파이썬] 미로 만들기 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력하는 문제이다. 그래프로 탐색을 하면서 특정 좌표에 도착하기까지 바꿔야 할 검은 방의 최소값을 갱신해가면 된다. 흰 방부터 생각해보자. 첫 번째 좌표인 (0, 0)에서는 바꿔야 할 검은 방의 개수가 0이다. 또한 이 첫 번째 좌표와 연결된 모든 흰 방의 좌표 역시 바꿔야 할 최소 검은 방의 개수가 0이다. 당연하게도 연결되어 있는 모든 흰 방의 좌.. 2023. 7. 31. [백준 13023][파이썬] DFS 구현 방법 DFS 구현 방식에는 여러 방법들이 존재하는데 DFS 문제를 풀 때마다 헷갈려서 이번에 확실하게 외우기 위해서 포스팅을 작성한다. https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 전형적인 DFS 문제이다. 연결 여부 가장 먼저 노드끼리 연결 여부를 판단해야 한다. 이 방법에는 크게 인접 행렬 방식과 연결 리스트 방식이 있다. 5개의 노드가 있다면 5x5 행렬을 만들어서 arr[a][b]가 True라면 a와 b가 연결되어 있다는 것을 의미한다. 1. 인접 행렬 위 문제에서 예제 입력1을 기준으로 행렬을 만들어보면 다음과 같다. 0 1 2 3 4 0 F.. 2023. 4. 10. 이전 1 다음 728x90 반응형
