본문 바로가기

백트래킹6

[백준 18428번] 감시 피하기 https://www.acmicpc.net/problem/18428import sysimport copyinput = sys.stdin.readline# NxN 크기의 공간에 선생님(T), 학생(S), 혹은 장애물(O)이 위치# 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표# 각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행# 선생님은 상, 하, 좌, 우 4가지 방향에 대하여, 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다# 단, 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다# 학생들은 복도의 빈 칸 중에서 장애물을 설치할 위치를 골라, 정확히 3개의 장애물을 설치# 결과적으로 3개의 장애물을.. 2024. 10. 5.
[백준 6603번] 로또 https://www.acmicpc.net/problem/6603import sysinput = sys.stdin.readline# {1, 2, ..., 49}에서 수 6개를 고른다# 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것def combinations(arr, k): cases = [] def dfs(elements,index): if len(elements) == k: cases.append(elements) return for i in range(index+1,len(arr)): dfs(elements+[arr[i]],i) dfs([].. 2024. 10. 3.
[백준 1469번] 숌 사이 수열 1469번: 숌 사이 수열 첫째 줄에 X의 크기 N이 주어진다. 둘째 줄에 X에 들어가는 수가 빈칸을 사이에 두고 주어진다. X의 크기는 8보다 작거나 같은 자연수이다. X의 원소는 0보다 크거나 같고 16보다 작거나 같은 정수 www.acmicpc.net import sys sys.setrecursionlimit(10**7) n = int(input()) # X의 크기는 8보다 작거나 같은 자연수 # X의 원소는 0보다 크거나 같고 16보다 작거나 같은 정수이다. # 사전 순으로 가장 빠른 것 x = sorted(list(map(int,input().split()))) s = [-1 for _ in range(n*2)] visited = [False for _ in range(17)] def dfs(i.. 2023. 9. 29.
[백준 9663번] N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이번 문제는 크기가 N x N 체스판 위에 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수를 구하는 문제이다. 본인은 체스를 좋아하지 않아서 룰을 잘 몰랐는데, 퀸은 상하좌우와 대각선에 있는 말을 공격할 수 있기 때문에 모든 말은 서로 상하좌우와 대각선에 배치할 수 없다. 일단 이 문제는 모든 경우의 수를 구하기 위해서 완전 탐색 기법 중 하나인 DFS를 사용하게 되면 14^14(1 2023. 9. 12.
[백준 15650번] N과 M(2) 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net n, m = map(int,input().split()) is_used = [False]*(n+1) temp = [] answer = [] def back(start): if len(temp) == m: answer.append(' '.join(map(str,temp))) return for i in range(start,n+1): if i not in temp: temp.append(i) back(i+1) temp.pop() back(1) for ans in .. 2023. 9. 11.
[백준 15649번] N과 M(1) 15649번: N과 M (1)한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해www.acmicpc.netn, m = map(int,input().split())is_used = [False]*9temp = []answer = []def backtracking(): if len(temp) == m: answer.append(' '.join(map(str,temp))) return for i in range(1,n+1): if not is_used[i]: is_used[i] = True .. 2023. 9. 11.

티스토리툴바