남남이루의 고군분투 🌳

노드가 추가될 때 마다, 그 인덱스를 출력하면 된다. 노드가 추가될 수 있다는건 루트 역할 하는 거고, 그 때 인덱스가 루트니까. import sys sys.stdin = open('input.txt','rt') input = sys.stdin.readline n = int(input()) tree = [[] for _ in range(n+1)] ans = [0] * (n+1) for i in range(n-1): a, b = map(int, input().split()) tree[a].append(b) tree[b].append(a) # print(tree) # [[], [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]] check = [False] * (n+1) ..

문제 트리 순회 출력하기 + 순회란, 노드와 간선(방향)으로 이루어진 트리를 어떤 순서로 탐색하는 지를 말한다. 이진 트리의 경우 꼭 가계도처럼 생겼는데, 가지의 상위에 있는 정점(노드)을 부모 노드라고 하고, 아래에 딸려있는 노드들이 짜-식들이다. 전위 순회는 기본적으로 부모 -> 왼쪽 자식 -> 오른쪽 자식 순서로 탐색한다. 중위 순회는 왼쪽자식 -> 부모 -> 오른쪽 자식, 후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 부모 순이다. 제일 깊은 데까지 가서 출력하는데, 진행 경로를 선으로 이어서 그려보면 이해하기 쉽다. import sys sys.stdin = open('input.txt','rt') input = sys.stdin.readline n = int(input()) dic = {} fo..

문제 고장난 리모컨으로 채널을 이동하자! 어려웠던 점 str으로 자릿수별로 숫자맞추면서 접근해야 하는 줄 알았는데, 완전탐색이어서 숫자 하나씩 올리면서 접근해야 한다. 의외로 구현하기가 어려웠다. abs() 절대값 함수를 쓰지 않으면 음수 체크(if x < 0: x* -1)를 해줘야 해서 훨씬 코드가 길어진다. 수의 범위 수의 범위가 채널 범위 500,000를 그대로 쓰면 안되고, 리모컨 입력 접근 방향을 고려해야하기 때문에 자리수가 다를 수 있어 1,000,000으로 설정해야 한다. 작은 수에서 큰 수로 이동할땐 500,000 로 반대로 큰수에서 작은수로 내려올 때는 1,000,000 까지 target = int(input()) ans = abs(100 - target) # ++ or -- 로 이동할 ..

문제 이 나라의 규칙에 맞는 날짜계산 방식으로 year를 구해라 year이랑 e, s, m 간의 관계에 대한 식을 쉽게 표현할 수록 풀이가 쉬워진다. 2 try - success import sys sys.stdin = open('../DFS/in.txt', 'rt') # input = sys.stdin.readline e,s,m = map(int, input().split()) def DFS(year): global e res = year res2 = year res3 = year while res > 15: res -= 15 if res != e: return False while res2 > 28: res2 -= 28 if res2 != s: return False while res3 > 19: r..

문제 토마토 익으려면 얼마나 걸려? 주의 : pypy로 해야지만 시간 초과가 안떴다. 난이도 : 다시보니, 훨 이해가 잘간다! import sys from collections import deque sys.stdin = open('./BFS/input2.txt','rt') input = sys.stdin.readline m,n = map(int, input().split()) g = [list(map(int, input().split())) for _ in range(n) ] queue = deque([]) # 1 한 놈 queue에 넣고 시작 for i in range(n): for j in range(m): if g[i][j] == 1: queue.append([i,j]) # print(queue)..

import sys sys.stdin = open('input.txt', 'rt') input = sys.stdin.readline # g[h][w] # w 열의 개수, # h 행의 개수, dx = [1,-1,0,0,1,-1,1,-1] dy = [0,0,1,-1,1,-1,-1,1] def DFS(x,y): global comp if 0

원리 텀프로젝트처럼 사이클 돌리고 그 길이랑, 그 길이 아닌거(포함 미포함)랑 구해서 최대값 구했는데 자꾸 사이클이 엄청나게 길어짐.. ㅇㅅㅇ # 두 번째 줄에 n개의 정수 xi (i = 1, 2, ... , n, 1 ≤ xi ≤ n) 가 순서대로 주어진다. xi는 xi번째 사람이 버스에 타지 않는다면 i번째 사람 역시 버스에 타지 않음을 의미한다. # 얘는 꼭 타야돼 import sys sys.stdin = open('in2.txt') sys.setrecursionlimit(10**5) input = sys.stdin.readline n, cap = map(int, input().split()) graph =[0] + list(map(int, input().split())) check = [False]..

(+) 이차원 배열의 max 찾기 방법 1. graph = [list(map(int, input().split())) for _ in range(N)] graph_min = min(map(min, graph)) # min_height graph_max = max(map(max, graph)) # max_height 방법 2. g = [] largest = 0 for _ in range(n): l = list(map(int, input().split())) largest = max(max(l),largest) g.append(l) 문제 영역 구하는 문제인데, 물의 수위를 조절하며 영역의 개수가 최대일 때를 찾아야 한다. 예시 답은 다 맞게 나오는데, 백준 저지에서 자꾸 틀린다... 왜지... 근데 왜 틀렸..

경로 찾는 문제, 방향이 있는 그래프 문제이다. DFS 선언 내부 for 문은 매개변수 v행 에 호응하는 열i 에 해당한다. 행 단위로 확인하기 때문에 visit이 2차원이 아니다. 또 visit을 반복문 내에서 출력하는 게 다른 DFS와의 차이점이다. 간단하지만 아직 연습이 더 필요한 문제이다. import sys sys.stdin = open('graph input.txt', 'rt') input = sys.stdin.readline size = int(input()) visit = [0 for i in range(size)] g = [list(map(int, input().split())) for _ in range(size)] def DFS(v): for i in range(size): if vi..

문제 : 그래프에서 사각형 좌표 입력받으면, 사각형을 제외한 부분의 넓이와 개수를 구하라 포인트 1. 좌표값과 행렬의 차이 2. DFS 3. 좌표값 두개로 사각형 그리기 xy 좌표따라 그래프 그리는 거에서 좀 걸렸다. 넓이까지 구하는 게 아니었으면 더 빨리 풀 수 있었는데, 넓이 구해야 돼서 범위를 모퉁이 +1 없이 정확하게 구해야해가지고 더 오래 걸렸다. 대신에 영역 연습, 행과 열 변수 연습에 좋았다.. import sys sys.setrecursionlimit(10**4) input = sys.stdin.readline m,n,k = map(int, input().split()) g = [[0]*(n) for _ in range(m)] for _ in range(k): # x y x y lx,ly,..