본문 바로가기

백트래킹18

[백준-골드2] 19236번 청소년 상어 (백트래킹, 구현, 파이썬) https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 처음으로 이틀 걸린 문제,,, - 물고기들이 움직일 때 작은 번호부터 차례대로 이동 가능 --> 이 때, 상어가 있는 칸은 위치 이동 불가, 그러나 상어가 이미 먹어서 빈칸은 이동이 가능하다 --> 이 부분때문에 이틀 걸린듯,,, --> 따라서 move_fish 함수를 구현할 때 현재 상어의 위치 파라미터도 함께 받아서 현재 상어의 위치도 고려해야함 - 물고기가 방향을 바꿔서 이.. 2022. 3. 23.
[백준-골드5] 15683번 감시(DFS, 완전탐색, 파이썬) https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net - 이 문제를 완전탐색으로 풀려면 일반적인 조합이나 순열로는 모든 경우의 수를 뽑아 낼 수 없다. - 따라서 나는 파이썬의 product를 사용해서 여러 리스트의 경우의 수를 뽑을 수 있었다. (아래 참고) https://blog.naver.com/gyfla810/222497483349 [파이썬] permutation 순열, combination 조합, product Permutatio.. 2022. 2. 16.
[백준-골드5] 1759번 암호 만들기(백트래킹, 파이썬) https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 22/02/08 O - 우선 입력받은 alpha 리스트를 정렬해줘야한다. 암호가 사전순이기 때문에 - 또한 암호가 사전순이기 때문에 abc bac 이건 불가능하다. --> 따라서 dfs에 start 파라미터를 이용해서 중복을 방지했다. - 그리고 암호에 같은 문자는 없으므로 if alpha[i] not in stack: 조건을 넣어서 중복을 방지했다. - dfs 함수의 종료조건은 stack이 암호의길이.. 2022. 2. 7.
[백준-실버2] 10819번 차이를 최대로(백트래킹, 파이썬) https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net - 백트래킹 연습해야해서 일단 백트래킹으로 구현했다. - 입력에 같은 숫자가 여러개일수도 있기 때문에 visited 배열을 이용해서 사용한 인덱스를 체크했다. (이 부분 때문에 틀렸었음) - 그리고 순서에 따라 값이 달라지기 때문에 dfs에 파라미터 없이 구현했다. - stack의 길이가 n과 같아지면 반복문을 통해 그 리스트의 값을 계산하고 max_val과 비교해서 업데이트한다. n = int(input()).. 2022. 2. 7.

티스토리툴바