본문 바로가기

알고리즘/DFS BFS15

[Python] 백준 14888 연산자 끼워넣기 🧑‍💻 [Python] 백준 14888 연산자 끼워넣기 Silver 1 - DFS DFS로 풀이를 했다 코드 min_num = 1e9 max_num = -1e9 N = int(input()) numbers = list(map(int, input().split())) operators = list(map(int, input().split())) def dfs(num_depth, total, plus, minus, multiply, divide): global min_num, max_num if num_depth == N: min_num, max_num = min(total, min_num), max(total, max_num) return if plus > 0: dfs(num_depth + 1, total.. 2023. 4. 7.
[Python] 백준 9663 N-Queen 🧑‍💻 [Python] 백준 9663 N-Queen Gold 4 - Backtracking Queen은 위, 아래, 오른쪽, 왼쪽, 대각선, 8 방면 모두 공격을 할 수 있다 N이 주어지고, 체스판 사이즈는 N x N 이고, N 개의 Queen을 넣었을 때 서로 공격할 수 없는 때의 경우의 수를 찾는 것 1차적으로 자세히 보면, 각 행과 열마다, Queen은 하나씩 배치할 수 있다 이 뜻은 굳이 체스판 자체를 안 만들어도 된다 board = [0, 3, 1, 4, 2] 아래 사진을 표현한 리스트 (board의 인덱스가 열/row, board의 값이 행/column) board 안에 있는 값들은 모두 달라야 한다 row (board의 인덱스) column (board의 값) 0 0 1 3 2 1 3 4 4.. 2023. 4. 5.
[Python] 백준 15650 N과 M 2 🧑‍💻 [Python] 백준 15650 N과 M 2 Silver 3 - Backtracking 쉽게 itertools의 combinations를 사용해서 풀 수 있는 문제다 하지만 Backtracking을 공부하고 싶어서 풀었던 문제다 기본적으로 if len(nums) == M: 을 통해서 재귀 함수의 base case를 만든다 안 만들면 무한 루프 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 backtracking(start)를 다시 돈다 여기서 중요한 것은, 수열이 오름차순이어야 한다는 것이다 그래서 재귀함수를 돌릴때마다 backtracking(start + 1)를 해야 한다 그렇게 하면, for문에서 전에서 backtracking() 했던 것보다, 큰 수부터.. 2023. 4. 2.
[Python] 백준 15649 N과 M 🧑‍💻 [Python] 백준 15649 N과 M Silver 3 - Backtracking 쉽게 itertools의 permutations를 사용해서 풀 수 있는 문제다 하지만 Backtracking을 공부하고 싶어서 풀었던 문제다 기본적으로 if len(l) == M: 을 통해서 재귀 함수의 base case를 만든다 안 만들면 무한 루프 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 dfs()를 다시 돈다 그리고 l.pop()을 해야, 리스트에 숫자가 사라지고, 다른 경우의 수를 넣을 수 있다 코드 백트래킹 사용 N, M = map(int, input().split()) l = [] def dfs(): if len(l) == M: print(" ".join(ma.. 2023. 4. 2.
[Python] 백준 1915 가장 큰 정사각형 🧑‍💻 [Python] 백준 1915 가장 큰 정사각형 Gold 2 - Backtracking 행렬을 순회하면서, 1을 찾게되면, 그 1에 대한 모든 경우의 수를 가지고 최소값을 구하는 것이다 예) 찾은 1을 기준으로 1X1 색종이를 덮을 경우 예) 찾은 1을 기준으로 2X2 색종이를 덮을 경우 예) 찾은 1을 기준으로 3X3 색종이를 덮을 경우 예) 찾은 1을 기준으로 4X4 색종이를 덮을 경우 예) 찾은 1을 기준으로 5X5 색종이를 덮을 경우 56번째 줄이 끝나면, 대부분의 1은 0으로 바껴져 있을 것이다 (만약 한 사이즈의 색종이를 5장을 넘기면, 1로 유지가 될 것이다) 코드 matrix = [list(map(int, input().split())) for _ in range(10)] count.. 2023. 3. 31.
[Python] 백준 1389 케빈 베이컨의 6단계 법칙 🧑‍💻 [Python] 백준 1389 케빈 베이컨의 6단계 법칙 Silver 1 - BFS BFS 를 사용하면서 풀었다 각 숫자, 즉 1부터 N까지의 숫자와 친구의 거리를 모두 구해야 한다 for i in range(1, N + 1) 과 for j in range(1, N + 1)인 2중 for문을 통해서 각 친구들 간의 거리를 구한다 코드 from collections import deque def bfs(start, end, link_num): queue = deque() queue.append((start, 0)) visited = [0] * link_num visited[start] = 1 while queue: current, score = queue.popleft() if current == .. 2023. 3. 29.
[Python] 백준 1967 트리의 지름 🧑‍💻 [Python] 백준 1967 트리의 지름 Gold 4 - DFS 두 노드 사이의 가중치들을 더했을 때에 가장 큰 숫자를 출력하는 것 여기서 1의 기준에서 가중치가 제일 큰 노드를 구한다 그 다음, 가중치가 제일 큰 노드를 시작으로 DFS를 하여, 제일 큰 가중치를 구한다 여기서 DFS를 하면 어디서든, 제일 끝에 있는 자식 노드에 가게 된다 문제풀이 첫 DFS를 한 후에,visited 리스트 다시 초기화 시켜야 한다 second_index = visited.index(max(visited))을 통해서 두번째 DFS를 할 때에, 시작 점을 찾는다 코드 import sys sys.setrecursionlimit(10 ** 9) def dfs(start, weight): for node, wei in.. 2023. 2. 16.
[Python] 백준 1520 내리막길 🧑‍💻 [Python] 백준 1520 내리막길 Gold 3 - DFS DFS는 확실히 알았으나, 이걸 어떻게 DP로 풀어야 할지 몰랐다 1) 50 ▶️ 35 ▶️ 30 ▶️ 27 ▶️ 24 ▶️ 22 ▶️ 15 ▶️ 10 2) 50 ▶️ 45 ▶️ 37 ▶️ 32 ▶️ 20 ▶️ 17 ▶️ 15 ▶️ 10 3) 50 ▶️ 45 ▶️ 37 ▶️ 30 ▶️ 25 ▶️ 20 ▶️ 17 ▶️ 15 ▶️ 10 위를 보면, 15 ▶️ 10 은 3 경로 모두 겹친다 그리고, 20 ▶️ 17 ▶️ 15 ▶️ 10은 2번과 3번이 겹친다 겹치는 부분은 한번만 탐색을 하면 된다 즉 이미 방문을 했다면, 10까지의 경로는 겹치는 것이다 즉 겹치는 경로를 굳이 한번 더 탐색할 필요가 없다 코드 import sys sys.se.. 2023. 2. 15.
[Python] 백준 24482 알고리즘 수업 🧑‍💻 [Python] 백준 24482 알고리즘 수업 Silver 2 - DFS DFS 문제이다 깊이 우선 탐색으로, 탐색을 할 때마다 1씩 더해주면 된다 연결이 아예 안 되어 있을 때에는 -1 이다 내림차순 문제풀이 DFS 코드를 짜면 된다 코드 import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline def dfs(start, count): visited[start] = count for cur in graph[start]: if visited[cur] == -1: dfs(cur, count + 1) N, M, start = map(int, input().split()) visited = [-1] * (N + 1) graph = [[].. 2023. 2. 14.

티스토리툴바