본문 바로가기
728x90

DFS37

[python] 백준 2668 숫자고르기 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제 해결 사이클을 만들어서 사이클에 속해 있는 원소를 모두 가져올 수 있는지 확인하는 문제 사이클에 들어가는지 확인은 bfs, dfs 모두 가능하다.(하지만 문제에서 dfs를 원하는것 같다.) 이전에 풀어봤던 문제와 비슷하다.(무슨 문제였는지는 까먹어서...ㅜㅜ) CODE def cycle(num): global visited, c,result c.append(num) nx = gr.. 2023. 4. 7.
[python] 백준 9466 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 해결 하나씩 돌아가며 그 안에 사이클이 있는지 확인한다. 사이클을 돌면서 한 번 지나간 index는 두 번 지나갈 필요가 없다.(만약 한 번 돌았을 때 사이클이 안만들어 졌으면 안만들어지는 것이다.) CODE import sys sys.setrecursionlimit(1000000) def cycle(num): global ans visited[num] = True c.append(num) new.. 2023. 4. 4.
[python] 백준 16637 괄호 추가하기 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 문제 해결 괄호는 소괄호만 사용 가능 사칙연산의 순서는 무시 (곱셈 우선 하는 것 무시) 왼쪽 부터 계산하면서 한 번 계산할 때 마다 뒤에 괄호로 계산 한 것과 안한 것 두가지 경우가 있음 dfs로 뒤에 괄호가 있어서 계산 한 경우와 괄호 없어서 이어서 계산하는 경우 두 가지로 계속 나눠가며 계산 최댓값을 구하기 CODE def operator(num1, oper, num2): i.. 2023. 3. 28.
[python] 백준 15683 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제 해결 문제가 많이 어려웠다.(다른 분들의 풀이를 참고했다.) 결국 cctv 종류당 이동할 수 있는 방법의 수가 정해져 있기 때문에 dfs, bfs를 이용한 완전탐색을 해야한다. 이 사실을 알고 cctv당 이동 할 수 있는 방법을 리스트 안에 구현을 하면 사실 끝이다. 완전 탐색 후 가장 적게 사각지대가 생긴 개수를 구하면 된다. CODE import sys input = sys.s.. 2023. 3. 19.
728x90