dfs

방향 없는 그래프 주어짐 -> 연결 요소(connected component) 개수 구하는 프로그램 아이디어그래프 탐색 (DFS/BFS)방문 못한 노드 하나라도 있다면 카운트 증가하고그 방문 못한 노드 (false 노드)에서 시작해서 다시 그래프 탐색false 노드 없을 때까지 그래프 탐색 반복 풀이 - DFS 사용import sysinput = sys.stdin.readlineN, M = map(int, input().split())graph = [[] for _ in range(N+1)]for _ in range(M): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u)visited = [False] * (N+..

풀이 1: DFS, 재귀이용 - RecursionErrordef dfs(x, y): visited[x][y] = True for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: nx, ny = x + dx, y + dy if 0 첫번째 풀이이다. DFS와 재귀를 사용하여 풀었더니 Recursion Error가 났다.Recursion Error: 재귀와 관련된 에러. 주로 Python이 정한 최대 재귀 깊이보다 더 깊어질 때.이 경우, 재귀를 사용하지 않도록 바꾸어야 한다.BFS를 사용해서 풀거나, 재귀 없이 DFS를 구현해야 한다. 참고 링크 : https://yesolz.tistory.com/entry/Python-%EB%B0%B1%EC%A..

그래프 탐색 문제로 DFS, BFS 둘다 사용하여 풀이가 가능하다.아래는 DFS를 활용한 풀이이다.  DFSn = int(input()) # 정사각형 모양의 지도의 크기 입력# 지도 입력 받기map_data = [list(map(int, input())) for _ in range(n)]visited = [[False] * n for _ in range(n)] # 방문 여부를 저장하는 배열 초기화def dfs(x, y): visited[x][y] = True # 현재 위치를 방문했음을 표시 count = 1 # 단지의 크기를 세기 위한 변수 초기화 for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: # 현재 위치에서 이동할 수 있는 방향에 대해 반복..

그래프 탐색 문제로dfs, bfs 둘다 사용이 가능하여 다양한 풀이가 가능한 문제다.   DFS: dictionary(인접리스트), 재귀 사용n = int(input()) # 컴퓨터의 수 (1~100 정수)m = int(input()) # 직접 연결되어있는 컴퓨터 쌍의 수graph = {i: [] for i in range(1, n + 1)} # 각 컴퓨터와 이어진 컴퓨터들을 저장할 그래프 초기화for _ in range(m): a, b = map(int, input().split()) # 직접 연결된 컴퓨터 쌍을 입력받음 graph[a].append(b) # a와 b를 연결하여 그래프에 추가 graph[b].append(a) # b와 a를 연결하여 그래프에 추가visited = ..

1. n, m, v 입력 받기 (띄어쓰기 입력)n, m, v = map(int, input().split())N(정점수), M(간선수), V(탐색 시작할 정점 번호) 2. 그래프 입력 받기 (노드 연결 정보) - 인접 행렬graph = [[0] * (n+1) for _ in range(n+1)]for i in range(m): a, b = map(int, input().split()) graph[a][b] = graph[b][a] = 1 정점 번호와 인덱스 일치시키기 위해 n+1로 초기화무방향 그래프이므로 graph[a][b] = graph[b][a] = 1 ** 그래프 출력하기def print_graph(graph): for row in graph[1:]: # 0번째 행과 열은 사용하..

DFS/BFS 를 위한 자료구조 기초 : 스택, 큐, 재귀함수탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정대표적인 탐색 알고리즘 DFS, BFS - 기본 자료구조인 스택과 큐에대한 이해 필요  스택스택 : 선입후출파이썬에서 스택을 이용할 때는 별도의 라이브러리를 사용할 필요가 없다.기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.append() 메서드는 리스트의 가장 뒤쪽에 삽입, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터 꺼내기 때문  큐큐 : 선입선출collections 모듈에서 제공하는 deque 자료구조를 활용하자.deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며que..