알고리즘

1️⃣ - 처음 생각한 풀이 3차원 배열을 만들어서 데이터를 넣는다. 전부 방문하면서 1일 경우, 주변 토마토들을 익힌다. 토마토를 익힐 수 없을 때, 반복을 종료하고 년도, 상태를 확인하고 출력한다 이런 식으로 풀이를 생각했었는데, 3차원으로 생각을 하려다보니 계속 복잡해지고 헷갈려서 자꾸 답이 틀려서 다른 방식을 찾아봤다. 2️⃣ - 두 번째 풀이 3차원 배열에서 1을 전부 queue에 담는다. - 담으면서 방문처리 bfs로 queue에 있는 좌표들을 빼면서 근처 좌표들을 queue에 다시 넣고 익히는 과정을 반복한다. - queue에 다음 좌표들을 넣을 때 년도를 같이 넣어준다. 바뀐 배열을 처음부터 비교해서 가장 큰 값 -1을 출력한다 from sys import stdin as s from co..

1️⃣ - 처음 생각한 코드 그래프에 경로를 전부 저장 bfs로 시작지점부터 경로 시작해서 이전 경로까지 거리를 계속 비교해가면서 더 작은 값을 저장 반복해서 마지막 최종 목적지 배열의 값 출력 from sys import stdin as s from collections import deque import heapq s = open('input.txt','rt') N = int(s.readline()) M = int(s.readline()) graph = {} for _ in range(M): start, end , dis = list(map(int,s.readline().split())) graph[start] = graph.get(start,[]) + [(dis,end)] start , end = ..

🕹️ - 신장 트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 🕹️ - 크루스칼 알고리즘 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때 필요한 알고리즘이다. 그리디 알고리즘으로 분류되고 기본적으로 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다. 이때 사이클을 발생 시킬 수 있는 간선의 경우, 집합에 포함 시키지 않는다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. - 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. - 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. 모든 간선에 대하여 2번의 과정을 반복한다. 1️⃣..

🚀 Union_Find(서로소 집합 자료구조) Union_Find 자료구조는 스택의 pop, push처럼 Union(합집합), Find(찾기) 연산으로 구성된다. Union 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다. - A와 B의 루트 노드 A`, B`를 각각 찾는다. - A`를 B`의 부모 노드로 설정한다.(B`가 A`를 가리키도록 한다.) 모든 Union 연산을 처리할 때까지 1번 과정을 반복한다. 실제로 구현 할 때는 A`와 B`중에서 더 번호가 작은 원소가 부모노드가 되도록 구현하는 경우가 많다. 초기 단계에서 각자 자기 자신을 부모로 가지도록 초기화 한다. Union 1,4 - 현재 각각 루트 노드가 1과 4이기 때문에 둘 중 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 ..

이 문제는 어려워서 정리 한다기 보다 인접리스트로 그래프를 만드는 것을 처음 접해서 기록 및 정리를 위해 작성한다. https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 처음 인접리스트를 배열로 구현한 코드 from sys import stdin as s s = open('input.txt','rt') n = int(s.readline()) graph = [[] for _ in range(n+1)] def preorder(num): if ..

📔 트리 구조 노드와 가지로 구성되고 각 노드는 가지를 통해 다른 노드와 연결된다. 트리에는 루트, 리프, 비단말 노드 , 자식, 부모, 형제, 레벨, 차수, 높이 등등의 용어들이 있다. 가장 위쪽에 있는 노드를 루트 가장 아래쪽에 있는 노드를 리프 루트에서 얼마나 멀리 떨어져 있는지 나타내는 레벨 각 노드가 갖는 자식의 수를 차수 루트에서 가장 먼 리프까지의 거리가 높이 📔 이진 트리의 검색 너비 우선 검색 낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법 깊이 우선 검색 깊이 우선 검색은 리프에 도달 할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 한다. 깊이 우선 검색의 세가지 종류의 스캔 방법 더보기 노드 방문 -> 왼쪽 자식 -> 오른쪽 자..