깊이우선탐색7 [BOJ] 3980. 선발 명단(Python) / DFS, Backtracking 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 11개의 포지션에 11명의 선수를 채웠을 때, 능력치의 합의 최댓값을 구하는 문제. # 42분 소요. (한 번에 통과, PyPy3 제출 기준 시간 1위 달성했다!) 사용 알고리즘 : Backtracking, DFS 순열 구하기 무난하게 순열 구하는 dfs 재귀로 접근해 가지치기하여 가짓 수를 쳐냈다. 원래 dfs 순열로는 11개 자리에 11명을 각각 다른 자리에 배치하는 경우의 수가 39,916,800개가 나오는데, Backtracking으로 가지치기하면 경우의 수가 1824개로 확연히 준다. perm 함.. 2021. 4. 15. [BOJ] 10451. 순열 사이클(Python) / DFS 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 N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하는 문제 # 23분 소요 사용 알고리즘 : DFS 실버 1 문제로 구현이 오래 걸리지 않았다. 방문 표시 배열 check과 총 사이클 갯수를 셀 cycle 변수를 만들었다. 가리키는 숫자 인덱스와 배열 인덱스를 일치시키기 위해 주어진 숫자 리스트를 받으며 앞에 [0]을 추가해줬다. 재귀로 현 숫자가 가리.. 2021. 4. 8. [BOJ] 16929. Two Dots(Python) / DFS 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구하는 문제다. # 23분 소요 사용 알고리즘 : DFS 깊이 우선 탐색 설명할 것이 없는 듯.. 아래 코드와 같이 모든 정점에서 dfs를 돌리며 재귀로 갈 수 있는 곳으로 나아간다. 격자 밖이거나 이동할 곳의 문자가 다르다면 continue 방문할 수 있는 곳에만 방문 표시하며 재귀로 나아가고 출발지에 다다르고, 이동 횟수가 4번 이상이면 "Yes"를 출력하고 종료한다. 모든 재귀가 끝나도 사이클.. 2021. 4. 6. [BOJ] 2239. 스도쿠(Python) / DFS 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 우리가 아는 그 스도쿠 게임이 맞다. 하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하는 문제이다. 사용 알고리즘 : DFS 맵을 인풋 받으며 0의 위치를 리스트에 담는다.(zeros) dfs 재귀로 depth == len(zeros)가 되는 순간 완성한 맵을 형식에 맞게 출력한다. 기본적인 dfs함수 틀에서 빈 자리에 1부터 9까지 숫자 중 가능한 숫자를 확인한다. 행 체크 : rowCheck() 함수에서 해당 행에서 같은 숫자 있으면 .. 2021. 4. 6. [BOJ] 2529. 부등호(Python) / DFS www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾는 문제 사용 알고리즘 : DFS 재귀로 순열 구현하기 간단한 DFS 문제로 순열을 구하고 들어오는 각 숫자가 부등호에 부합하는 경우에만 재귀로 수를 더하며 넘기고, 부등호에 맞지 않다면 그냥 넘어간다.(isSatisfy 함수에서 확인) 가능한 경우일 때마다 최솟값, 최댓값을 갱신한다. 출력 시, 최댓값은 그대로 출력, 최솟값은 맨 앞 자리.. 2021. 4. 5. [BOJ] 13023. ABCDE(Python) / DFS www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 깔끔한 DFS 문제였다. input 받으면서 정점별로 갈 수 있는 정점의 정보를 딕셔너리에 담는다. 전역변수 flag를 두어 depth가 4이상 되면 1로 바꿔주며 return하여 더이상 진행하지 않는다. 모든 정점에서 start할 수 있다. visited로 아직 방문하지 않는 곳에 방문체크하며 다음 재귀로 넘어간다. 재귀 풀려 나올 땐 방문체크한 것을 0으로 돌려 놓는다. flag가 1이면 1, 0이면 0을 출력한다. 파이썬 코드는 다음과 같다. import sys input = sys.stdin.readline .. 2021. 3. 23. 이전 1 2 다음
