본문 바로가기
728x90
반응형

DFS9

2022.04.24 [백준] (python 파이썬) N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 https://blog.encrypted.gg/945 [실전 알고리즘] 0x0C강 - 백트래킹 이번에는 백트래킹을 배워보도록 하겠습니다. 백트래킹도 재귀와 더불어 많은 사람들이 고통을 호소하는 알고리즘 중 하나이지만 의외로 그 재귀적인 구조에 매료되어서 참재미를 알아버리는 blog.encrypted.gg 해당 문제는 위의 블로그에서 공부한 후, 참고하여 해결했습니다. 이 문제를 해결할 때, 퀸이 놓일때마다 .. 2022. 4. 24.
2022.03.03 [백준] (python 파이썬) 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 다음 문제는 1,2,3을 더해서 n을 만들 수 있는 가지 수를 구하는 문제이다. 1,2,3이 중복해서 사용해도 되고, 갯수 제한이 없다. 그래서 dfs를 이용하여 코드를 작성했다. for문안에 cnt배열을 만들어 각 케이스를 실행할 때, 초기화 되도록 만들었다. dfs함수는 sum==target이면 cnt[target]가 카운팅된다. 그리고 만약 sum>target이면 범위를 넘었기 때문에 return시켜준다. 아래의 코드를 각 상황마다 배열을 초기화시켜주고 dfs함수를 돌린다. 1 2 3.. 2022. 3. 3.
2022.03.01 [프로그래머스] (python 파이썬) 타겟 넘버 https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 풀이 dfs를 활용하여 각 배열의 부호가 +,-일때의 경우를 생각해서 코드를 작성했다. dfs의 파라미터는 들어간 숫자의 갯수, 들어간 숫자의 합으로 지정했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def solution(numbers, target): answer=0 def dfs(a,sum): nonlocal an.. 2022. 3. 1.
2022.02.14 [백준] (python 파이썬) DFS와 BFS 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를 모두 사용하여 답을 구하는 문제이다. 먼저 각 정점과 연결된 정점들을 graph에 저장한다. 문제에서 연결된 정점들이 많으면 번호가 작은거 부터 방문하라고 했으니 각각의 graph를 sort로 정렬해 준다. dfs함수를 먼저 실행시켜주고 bfs함수를 실행하기 전, vis배열을 초기화 시켜준다.(dfs함수를 실행하면서 이미 사용.. 2022. 2. 14.
728x90
반응형

티스토리툴바