백준 1707 파이썬 모든 노드로 각각 DFS탐색

백준 1707 - 이분 그래프 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 답안 코드 : import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N = int(input()) IsEven = True def DFS(node): global IsEven visited[node] = True for i in A[node]: if not visited[i]: check[i] =..

2024.06.05

백준 1033 파이썬 DFS와 최대공약수

백준 1033 - 칵테일 문제 https://www.acmicpc.net/problem/1033 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 답안 코드 : N = int(input()) A = [[] for _ in range(N)] visited = [False] * (N) D = [0] * (N) lcm = 1 def gcd(a, b): if b == 0: return a else: return gcd(b, a % b) def DFS(v): visited[v] = True for i in A[v]: n..

2024.06.03

백준 2178 파이썬 DFS보다 BFS를 쓰는 이유

백준 2178 - 미로탐색 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 답안 코드 : from collections import deque dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] N, M = map(int, input().split()) A = [[0] * M for _ in range(N)] visited = [[False] * M for _ in range(N)] for i in range(N): numbers = list(input(..

2024.05.17

백준 1260 파이썬 DFS와 BFS를 구현할 수 있는가

백준 1260 - DFS와 BFS 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 답안 코드 : from collections import deque N, M, Start = map(int, input().split()) A = [[] for _ in range(N + 1)] for _ in range(M): s, e = map(int, input().split()) A[s].append(e) # 양방..

2024.05.16

백준 13023 파이썬 DFS의 시간 복잡도 O(V+E)

백준 13023 - ABCDE 문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 답안 코드 : import sys sys.setrecursionlimit(10000) input = sys.stdin.readline N, M = map(int, input().split()) arrive = False A = [[] for _ in range(N + 1)] visited = [False] * (N + 1) def DFS(now, depth): global arrive if depth == 5 or arrive == True: # 깊이가 5가 되면 종..

2024.05.15

탐색 알고리즘 정리

탐색 탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 말한다. 주어진 데이터의 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하고, 실제 모든 코딩 테스트 문제의 기본이 되는 알고리즘이므로 직접 구현해 원리를 완벽하게 이해하는 것이 중요하다. 탐색 영역에서는 그래프를 자주 탐색하므로 아래 저의 블로그를 참고하고 보면 좋을 것 같습니다. https://mkisos.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%98-%ED%91%9C%ED%98%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0 깊이 우선 탐색 깊이 ..

2024.02.11