깊이우선탐색 (12) 썸네일형 리스트형 [백준] 바닥 장식(python) 백준, 바닥 장식 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net TL;DR 그래프 탐색 깊이 우선 탐색(DFS) 문제 요약 1. 바닥 장식을 위해서 필요한 나무 판자의 개수를 구하는 프로그램이다. 2. -가 같은 행에 위치한다면 하나의 나무 판자로 만들 수 있다. 3. |가 같은 열에 위치한다면 하나의 나무 판자로 만들 수 있다. - 섬의 개수 문제의 응용 버전이다. -일 때는 인접한 행에 동일한 것이 있는지 확인하면 되고 |일 때는 인접한 열에 동일한 것이 있는지 확인하면 된다. 입출력 형태 예시 3 :: 같은 .. [백준] 연결 요소의 개수(python) 백준, 연결 요소의 개수 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net TL;DR 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 문제 요약 1. 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 프로그램을 작성하시오. - 모든 노드 사이의 움직일 수 있는 무향, 양방향 그래프가 주어질 때, 연결 요소의 개수를 구하는 프로그렘을 작성해야 한다. (연결 요소에 대해서는 입출력 형태에서 확인한다.) 입출력 형태 주어진 그래프를 그림으로 표.. [프로그래머스] 소수 찾기(python) Programmers, 소수 찾기 TL;DR DFS(깊이 우선 탐색) 문제 요약 1. 한 자리 숫자가 적힌 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내는 함수를 작성하라. - 주어진 숫자들로 만들 수 있는 모든 경우의 숫자들 중에서 소수의 개수를 반환하는 프로그램을 찾으면 된다. - 깊이 우선 탐색(DFS)을 사용해서 만들 수 있는 숫자들의 조합을 찾으면 문제를 해결할 수 있다. 입출력 형태 풀이 import math def solution(numbers): answer = 0 permutations = set() prev_elements = [] def dfs(elements): if ''.join(prev_elements) != '': permutations.add(int(''.join(p.. [리트코드] Balanced Binary Tree(python) 리트코드, Balanced Binary Tree_균형 이진 트리 TL;DR 트리(Tree) 깊이 우선 탐색(DFS) 문제 요약 1. 주어진 이진 트리가 높이 균형이 맞는지 아닌지를 판별하는 프로그램을 작성하라. 2. 높이 균형이 맞는 이진 트리는 모든 노드들의 왼쪽 및 오른쪽 서브 트리의 높이 차이가 1을 초과하지 않는 트리를 의미한다. - 형제 노드 간의 차이가 1을 초과하지 않을 때는 True를, 그렇지 않은 경우에는 False를 반환하면 된다. 입출력 형태 - 예시 1의 경우 모든 서브트리에서 높이 차이가 최대 1이다. 그렇기 때문에 True를 반환하였다. - 예시 2의 경우 가장 하위에 있는 서브트리와([3, 4, 4])가 루트의 서브트리([1, 2, 2])와 높이 차이가 1을 초과하기 때문에 f.. [리트코드] Reconstruct Itinerary(python) 리트코드, Reconstruct Itinerary_경로 재구성 TL;DR 깊이 우선 탐색(DFS) 문제 요약 1. 출발지와 도착지가 [출발지, 도착지] 형태로 주어진 배열에 대해서 경로를 재구성해서 반환하여라. 2. 'JFK'에서 출발하기 때문에 모든 입력에는 'JFK'가 있는 것이 보장된다. 3. 존재하는 여러 경로 중 가장 최소의 알파벳 순서로 된 경로를 반환해야 한다. 4. 모든 티켓은 최소 하나의 유효한 경로가 존재하며, 하나의 티켓은 한 번만 사용해야 한다. - 모든 티켓을 사용하여 만들 수 있는 경로 중 가장 최소이며, 알파벳 순서로 돌아다니는 경로를 반환하면 된다. 입출력 형태 - 예시 1의 경우, 그림에서 주어지는 그림과 같이 순서대로 이동하는 것이 유효한 최소 알파벳 순서의 경로이다. -.. [리트코드] Subsets(python) 리트코드, Subsets_부분집합 TL;DR 깊이 우선 탐색(DFS) 문제 1. 주어진 중복이 없는 정수 배열 nums에 대해서 생성할 수 있는 모든 부분 집합을 반환하라. 2. 정답 배열은 복사된 부분 집합을 포함해서는 안되며 정렬 순서에는 큰 상관이 없다. 입출력 형태 - 주어진 숫자 배열로 만들 수 있는 모든 부분 집합을 반환하면 된다. - 공집합 또한 부분 집합의 일부이므로 포함시켜야 한다. 풀이 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: answer = [] def dfs(index: int, subsets: List[int]): answer.append(subsets) for i in range(index, l.. [리트코드] Combination Sum(python) 리트코드, Combination Sum_조합의 합 TL;DR 깊이 우선 탐색(DFS) 문제 1. 주어진 구분된 정수 배열 candidates와 목표 정수 target에 대해서 조합한 숫자들의 합이 target이 되는 유일한 조합들의 배열을 반환해야 한다. 2. candidates 내에 동일한 숫자를 여러 번 고를 수 있으며, 만약 적어도 하나의 숫자가 다르다면 두 조합은 다른 조합이다. 3. 문제에서 target이 되는 조합의 수가 150보다 적은 것을 보장한다. - 주어진 정수 배열 candidates 내에 있는 숫자를 중복 선택한 조합들에 대해서 조합의 합이 target이 되는 배열을 반환하면 된다. 입출력 형태 - 주어진 정수 배열 [2, 3, 6, 7]에서 합이 7이 되도록 숫자를 조합하는 경우는.. [백준] DFS와 BFS(python) 백준, DFS와 BFS TL;DR 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 문제 분석 1. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 2. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고 3. 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 4. 정점 번호는 1번부터 N번까지이다. - 입력으로 주어진 그래프를 DFS와 BFS로 각각 순회한 결과를 출력하는 프로그램을 작성하는 문제이다. - 2번의 조건에 유의하여 문제를 풀어야 한다. 입출력 형태 - 가장 첫 번째 줄에 정점(vertex, node)의 개수와 간선(edge)의 개수, 그리고 시작 정점의 번호가 주어진다. - 두 번째 줄부터는 각 정점 간의 연결관계를 나.. 이전 1 2 다음
