해킹왕 양선규

import sys sys.setrecursionlimit(10 ** 9) # 재귀함수 최대깊이 늘려놓기 N, M = map(int, sys.stdin.readline().split()) # 노드개수, 간선개수 graph = [[] for _ in range(N + 1)] # 노드번호와 인덱스를 맞추기 위해 + 1 for _ in range(M): # 연결정보 입력받기 root, edge = map(int, sys.stdin.readline().split()) graph[root].append(edge) graph[edge].append(root) visited = [False] * (N + 1) # 노드번호와 인덱스를 맞추기 위해 + 1 visited[0] = True # 마지막에 False 존재 여부..

import sys sys.setrecursionlimit(10 ** 9) N = int(sys.stdin.readline()) # 노드의 개수 graph = [[] for _ in range(N + 1)] # 노드번호와 인덱스번호 동기화를 위해 N + 1 for _ in range(N - 1): # 연결정보 입력받기 root, edge = map(int, sys.stdin.readline().split()) graph[root].append(edge) graph[edge].append(root) visited = [False] * (N + 1) parent = [[] for _ in range(N + 1)] # 노드번호와 인덱스번호 동기화를 위해 N + 1 def dfs(graph, v, visited..

# DFS/BFS로 모든 노드 탐색 # visited 목록 만들어서 True 갯수 세면 될듯 !! import sys N = int(sys.stdin.readline()) # 노드의 개수 E = int(sys.stdin.readline()) # 간선의 개수 graph = [[] for _ in range(N + 1)] # 노드번호와 동기화 하기 위해 N + 1 for _ in range(E): root, edge = map(int, sys.stdin.readline().split()) # [1,2] 형태로 입력된다. 1번과 2번에 연결되어 있다는 뜻 graph[root].append(edge) # 무방향(양방향) 그래프이기 때문에 대칭되게 입력해 준다 graph[edge].append(root) for ..

from collections import deque import sys def DFS(graph, v, visited): # 인접노드리스트, 시작 노드, 방문목록 visited[v] = True print(v, end=' ') for i in graph[v]: # 현재 노드의 인접 노드로 재귀 if visited[i] == False: # 아직 안 갔으면 가기 DFS(graph, i, visited) def BFS(graph, start, visited): # 인접노드리스트, 시작 노드, 방문목록 queue = deque([start]) # 큐에 시작 노드 넣기 visited[start] = True while queue: v = queue.popleft() # 큐에서 노드 빼고 출력 print(v, ..

스택(Stack) - 후입선출(Last In First Out) 구조 - 마지막에 들어온 데이터가 가장 먼저 나간다 - 파이썬에서는 리스트와 pop(), append() 메소드로 스택을 구현할 수 있다 큐(Queue) - 선입선출(First In First Out) 구조 - 먼저 들어온 데이터가 가장 먼저 나간다. “공정한 자료구조” - from collections import deque 사용해서 deque 자료구조를 활용하는 게 좋다 - deque는 스택, 큐의 장점을 모두 채택한 것인데 리스트에 비해 빠르고 queue 라이브러리를 이용하는 것 보다 간단하다 - append(), popleft()를 이용하여 큐를 구현할 수 있다 DFS(Depth-First Search, 깊이 우선 탐색) - 그래프에..

def dfs(graph, selected, m): # 숫자목록, 현재선택된숫자리스트, 모을 숫자의 개수 if len(selected) == m: # 선택된 숫자가 m개면 출력 print(*selected) # ex) [1, 2, 3] -> 1 2 3 이렇게 출력됨 return # 출력을 했으면 상위 노드로 돌아가 다른 경우의 수 찾음 for i in range(1, len(graph)): # 1부터 n까지 탐색 if not visited[i]: # 방문 안했었다면 값 추가, 이 숫자를 점유한다는 느낌 visited[i] = True # 숫자는 중복되면 안 되니까, 하위 노드에서 이 숫자를 쓰지 않도록 True로 해둔다(점유한다) selected.append(i) dfs(graph, selected, m..