본문 바로가기
728x90

DFS37

[python] 백준 17616 등수 찾기 https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 문제 해결 DFS로 내 앞에 최소 몇명이 있는지 구하고, 내 뒤에 최소 몇명이 있는지 쉽게 구할 수 있다. 최고 등수는 한 명도 앞에 없을 때 1등이라 하고 앞에 있는 사람의 명수가 늘어날 때마다 1씩 더해준다. 최저 등수는 꼴등이라 가정하고 뒤에 한 명씩 단서가 생길 때마다 1씩 빼주며 등수를 구한다. 함께 구하는 방법은 생각하지 .. 2023. 8. 11.
[python] 백준 1949 우수 마을 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,00 www.acmicpc.net 문제 해결 이웃한 마을, 즉 연결되어있는 지역으로 가면 안된다는 것이 어려운 부분이다. 이를 dp[i][0], dp[i][1] 로 두가지로 나눠서 i번째 마을을 포함하지 않은 누적 최대합과 i번째 마을을 포함하는 누적 최대합으로 나눠서 계산을 한다. 그럼 어떻게 모든 마을의 경우의 수를 계산하는가? dfs(깊이 우선 그래프)를 이용해 모든 마을을 순찰하면서 최대 합을 구할 수.. 2023. 5. 7.
[python] 백준 16987 계란으로 계란치기 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 문제 해결 전형적인 백트래킹 문제 하나씩 차례로 부딪힐 수 있는 것을 부딪히고 다음 것을 부딪히고 하다가 끝까지 간후 다시 부딪히기 전으로 합치고 다음 것부터 부딪히고 모든 경우의 수를 계산해야한다. CODE n = int(input()) S = [] for _ in range(n): a, b = map(int, input().split()) S.append([a,b]) def df.. 2023. 4. 18.
[python] 백준 1941 소문난 칠공주 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제해결 조건이 4가지를 만족해야하므로 차례대로 만족시킬 수 있는 방법이 뭔지 생각해본다. 1번과2번조건을 묶고 3번과 4번 조건을 묶으면 좋다. 7명의 여학생으로 구성되어있어야하므로 depth=7인 dfs를 사용하면 좋을 것 같다. (게다가 가로 또는 세로로 인접해 있어야하므로 dfs로 이동하는 것은 좋다.) 임도연파가 4명 이상이면 안되는 것이기 때문에 중간에 그만두고 다른 것을 찾도록 한다. b.. 2023. 4. 18.
728x90