728x90 dfs 썸네일형 리스트형 [백준알고리즘] 1260번: DFS와 BFS -Python [백준알고리즘] 1260번: DFS와 BFS -Python https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net DFS와 BFS를 한 문제에서 동시에 해결해야 하는 문제이다. 여러 경로가 가능한 경우 중에서 작은 번호의 정점을 우선 선택했을 때의 경로들을 출력하면 된다. 예에에에에전에 Java로 풀었던 적이 있는 문제이기도 하고 기본 DF.. 더보기 [백준알고리즘] 14888번: 연산자 끼워넣기 -Python [백준알고리즘] 14888번: 연산자 끼워넣기 -Python https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 백트래킹 문제이다. 왜지? 그냥 DFS 문제이다. 단계별 풀기에는 분명 백트래킹으로 되어있는데 페이지 밑에 알고리즘 분류에는 또 브포로 나와있다.. 주절주절했듯이 그냥 모든 경우를 찾아야한다. 가지치기(pruning)할 경우를 나눈다고 해.. 더보기 [백준알고리즘] 15649번: N과 M (1) -Python [백준알고리즘] 15649번: N과 M (1) -Python https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 오랜만에 백준에 들어가니 BackTracking이 있었다. 예전에도 있었나 모르겠지만 처음 본 것 같아서 풀어봤다. 근데 1번째 문제라 그런지 백트랙킹 문제라기보다는 DFS 같았다. 그래서 그냥 DFS로 풀었다. :) 두 가지 방법으로 풀었는데 첫 번째는 DFS로 풀었고 두 번째 풀이는 itertools 모듈을 이용해서 풀었다.. 더보기 [백준알고리즘] 1520번: 내리막 길 -Python [백준알고리즘] 1520번: 내리막 길 -Python https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다. www.acmicpc.net 20200408 아래 새로 풀었다. 요즘 계속 DP를 다시 보고 있다. 오늘은 내리막 길을 풀어봤는데 금방 풀렸다. 개인적으로 dp 중에서는 쉬운 편이었다고 생각을 한다. 이번에는 최저의 방법을 구하는 것이 아닌 가능한 경우의 횟수를 구하는 문제다. 그러다.. 더보기 이전 1 ··· 3 4 5 6 다음
