본문 바로가기

dfs26

[백준-골드4] 1707번 이분 그래프(BFS, 파이썬) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net [이분 그래프란?] - 이분 그래프는 각 노드에 속하는 어떤 노드도 서로 인접하지 않은 그래프이다. - 아래 그림을 보면 각 노드에 속하는 노드끼리 서로 색깔이 다른것을 확인 할 수있다. - visited 배열을 이용해서 1과 -1로 인접 노드와의 색깔을 구분해주었다. - 각 노드와 인접한 노드를 돌면서 아직 방문하지 않은 경우 순회중인 노드의 visited를 -로 표시해준다. - 만약 노드와 노.. 2022. 2. 18.
[백준-골드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] 15666번 N과 M(12) (백트래킹, 파이썬) https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net - 드디어 N과 M 마지막 문제,, 이거 풀면 백트래킹 달인 될줄 알았는데,,, 다른문제 풀때 완전탐색이 더 편하다 ㅎ 이게 맞나,,ㅎ - 이번 문제는 같은 수를 고르는 것 허용 (1 1, 7 7 허용) - 순서고려함 (1 7 7 1 중 1 7 허용) n, m = map(int, input().split()) nums = list(map(int, input().split())) stack = .. 2022. 2. 7.

티스토리툴바