본문 바로가기

백트래킹18

[백준-실버3] 15654번 N과 M(5) (파이썬, 백트래킹, DFS) https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 22/03/05 O - 이번문제는 앞에 1-4번과 다르게 자연수 n을 주는것이 아니라 특정 숫자를 입력으로 주었다. - 따라서 입력받은 숫자를 리스트 nums에 담고 리스트를 반복하면서 dfs를 구현하였다. - 또한 출력결과 같은숫자의 중복을 허용하지 않았다 1 1, 2 2 -> 안됨 그래서 if num not in stack: 조건으로 같은 숫자의 중복을 방지하였다. - 순열이므로 df.. 2022. 2. 6.
[백준-실버3] 15652번 N과 M(4) (파이썬, 백트래킹, DFS) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 22/03/05 O - 이번 문제는 같은 수의 중복은 허용 (1 1 , 2 2) - 순서를 고려하지 않음 (1 2 2 1 둘다 허용하지 않고 1 2 만 가능) - 따라서 dfs함수에 start 파라미터를 이용하였고, dfs(i+1)을 호출하여 조합을 구현하였다. - if i not in stack: 조건은 필요하지 않음 -> 이 조건이 붙으면 1 1 출력 못함 n, m = map(int, inp.. 2022. 2. 6.
[백준-실버3] 15651번 N과 M(3) (파이썬, 백트래킹, DFS) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 22/03/05 O - 이번 문제는 모든 중복을 허용한다. - 이전에 문제에서는 1 1, 2 2 이런게 허용이 안됐는데 이번에는 허용 가능 - 따라서 반복문을 돌면서 조건문 없이 바로 스택에 추가하였다. - 이전 문제에서는 if i not in stack: 조건이 있었는데 이번문제에는 그 조건을 삭제함으로써 중복을 허용하였다. n, m = map(int, input.. 2022. 2. 6.
[백준-골드4] 1987번 알파벳(BFS, 파이썬) https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net - 큐를 set을 활용해서 중복을 방지하였다. - 현재 알파벳을 기록해주고 현재 알파벳이 이동할 곳에 아직 없을때만 이동해서 지난 알파벳은 방문하지 않는다. import sys r,c = map(int, input().split()) graph = [] for _ in range(r): graph.append(list(input())) dx = [0,0,1,-1] dy = [1,-1,0,0.. 2022. 1. 14.

티스토리툴바