PS25 [BOJ] Python 백준 Yes or yes(25195) https://www.acmicpc.net/problem/25195 백트래킹을 통한 뚫린 길 찾는 완전 탐색 문제이다.결론적으로 팬이 있는 길을 피해 끝까지 도달해야함으로끝 도달 판단, 팬이 있는지 검증이 중요하다. 문제에서는 사이클이 존재하지 않는다고 했으므로, 끝으로 도달 하는 판단은 s[v]가 비어있으면 끝에 도달했다고 판단하면 된다.이를 통해 팬 없이 s[v]가 0인 곳까지 오면 팬 없는 길이 존재한다는 뜻이 된다.import sysinput = sys.stdin.readlinesys.setrecursionlimit(1000000)N,M = map(int,input().split())s= [[] for _ in range(N+1)]visited = [False] * (N+1)for _ in ra.. 2024. 11. 8. [BOJ] Python 백준 특정 거리의 도시 찾기(18352) https://www.acmicpc.net/problem/18352 bfs로 푸는 최단거리 문제이다. bfs로 방문하며, 이전 방문값에 +1한 값을 더하여 최종적으로 X에서 출발했을때, 거리가 K인 값을 찾는 문제이다.import sysinput = sys.stdin.readlinefrom collections import dequeN, M, K, X = map(int,input().split())s = [[] for _ in range(N+1)]visited = [-1] * (N+1)for _ in range(M): u,v = map(int,input().split()) s[u].append(v)def dfs(n,v): if n > K: return for i in .. 2024. 11. 7. [BOJ] Python 백준 촌수계산(2644) https://www.acmicpc.net/problem/2644 전형적인 특정 값 사이의 dfs 깊이 구하기 문제import sysinput = sys.stdin.readlineN = int(input())target1, target2= map(int,input().split())visited = [False] * (N+1)s = [[] for _ in range(N+1)]M = int(input())for _ in range(M): u,v = map(int,input().split()) s[u].append(v) s[v].append(u)chk = Falsedef dfs(n, start, end): global chk visited[start] = True if sta.. 2024. 11. 4. [Progammers] Python 프로그래머스 모음사전(84512) https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해시와 dfs를 조합하는 백트래킹 문제이다.문자열을 해시로 저장하여 만약 해당 문자열이 있는 경우 방문처리를 하여 조건에 걸리지 않도록 중복없는 완전탐색을 진행cnt = 0result = 0text = ""s_dict = {}def dfs(n, s): global cnt, result, text if s == text: result = cnt return if len(s) == 5: ret.. 2024. 11. 3. 이전 1 2 3 4 5 6 7 다음