그래프

[python] SWEA - 1248. 공통조상

🤔문제 해결 D5 | 그래프 이진 트리를 만들어서 문제를 해결하자. 이런식으로 2차원 배열을 만든다. 길이가 3인 리스트가 V개인 2차원리스트 부모 노드들 찾기첫 노드 (여기서는 8 과 13) 에서 시작해서 부모 노드를 타고 쭉 올라간다. ( DFS ) 8 의 부모 노드는 [5, 3, 1] 13의 부모 노드는 [11, 6, 3, 1] 공통 부모 노드 찾기 앞에서부터 for문을 돌며 겹치는 친구 찾고 바로 나오기 (여기서는 3) 공통 부모 노드 크기 찾기 노드(여기서는 3)에서 자식 노드를 타고 쭉 내려가면서 개수를 세어준다(DFS) 💨 💻소스 코드 def find_parent(n, parent_list): if tree[n][2]: parent_list.append(tree[n][2]) find_pare..

[python] 백준 - 1926. 그림

🤔문제 해결 S1 | BFS, 그래프 그림을 하나 선택 한다. 그 그림의 상하좌우를 탐색한다. 만약 상하좌우에 그림이 있다면 그 그림을 선택 후 다시 상하좌우 선택한다. 더 이상 처음 선택한 그림과 연결된 그림이 없을 때 까지 탐색. 위의 과정을 반복한다. 처음 그림을 선택하면 그림의 갯수 +1 그림선택후 상하좌우 탐색하면서 그림을 찾으면 그림의 크기 +1 💨 기본적인 BFS 문제 💻소스 코드 from collections import deque def bfs(x, y): q = deque() q.append((x, y)) images[i][j] = 0 size = 1 # 최초 들어갈 때 그림 크기 1로 시작 while q: x, y = q.popleft() for k in range(4): # 상하좌우..

[python] 백준 - 1743. 음식물 피하기

🤔문제 해결 S1 | BFS 이번에는 2차원리스트를 활용하지 않고 set()을 활용하여 문제를 해결했다. 각각의 좌표가 주어져 있으므로 쓰레기를 하나 선택해 상하좌우 BFS탐색을 한다. 주변의 쓰레기를 선택할 때마다 visited 에 add 해준다. 또 count + 1 을 해줘서 쓰레기 더미의 크기를 answer 에 담는다. 💨 set() 을 쓰는 이유 if tmp in set() : 이렇게 tmp가 set()에 있는지 없는지 확인할 때 시간복잡도가 O(1) 이다. 하지만 if tmp in list : list의 경우 O(n) 이다. 💻소스 코드 import sys from collections import deque def bfs(x, y): q = deque() q.append((x, y)) cnt..

[python] 이진 트리 (binary tree) - 개념 정리

📗 이진 트리 (binary tree) 이진트리란 최대 두 개의 자식(없을 수도 있음)을 가지는 트리 형태의 자료구조이다. 탐색을 하거나 정렬을 하는데 있어 매우 효율적으로 사용된다. 탐색의 시간복잡도는 평균적으로 O(logn) 이다. 🔵 이진 탐색 트리(binary search tree) 이진 탐색 트리는 이진 트리의 하나이다. 노드에 대해서 왼쪽 자식의 값은 노드의 값보다 작거나 같고, 오른쪽 자식은 노드의 값보다 크다. 아래의 그림을 보면 [21, 28, 14, 32, 25, 18, 11, 30, 19, 15]의 순서대로 이진 탐색 트리를 구현하는 과정을 나타내고 있다. 가장 처음의 값은 root 노드가 되고, 다음 값부터 노드와의 대소 비교관계에 따라 위치를 결정한다. 🔵 이진 탐색 트리 Sear..

[python] SWEA - 1238. [S/W 문제해결 기본] 10일차 - Contact

🤔문제 해결 1. D4 | BFS 2. 주어진 인풋값으로 인접리스트를 만든다. 3. 똑같은 노드를 탐색하는 것을 막기 위해 방문여부를 확인할 visited 리스트, BFS에서 같은 깊이에서 가장 큰 숫자를 기억해둘 result를 만들고 deque를 이용해 BFS 탐색을 한다. 4. 재귀 함수를 이용해서 BFS의 깊이마다 result의 값을 갱신해준다. 5. 마지막으로 갱신된 result 를 출력 💨 💻소스 코드 from _collections import deque def contact(current_q): global result # 마지막 연락받은 사람들 중 가장 큰 값 result = max(current_q) # 다음 연락 받을 사람들이 들어갈 리스트 next_q = deque() # 현재 연락받..

[python] SWEA - 7465. 창용 마을 무리의 개수 / 10200. 구독자 전쟁

1. 창용 마을 무리의 개수 문제 해결 D4 | DFS, BFS, 그래프 1. 주어진 정보로 인접리스트를 만든다. 2. 보통의 그래프 탐색이라면 시작점하나로 BFS나 DFS 탐색을 하고 끝나지만 여기서는 모든 노드를 탐색해야 하므로 3. BFS탐색을 하는 while문을 for문으로 감싸서 모든 노드를 탐색한다. 4. for문을 통해 큐에 들어가는 노드는 한 무리의 시작점이므로 카운트를 세어준다. 🌦 처음 실패는 while 문 안에 for 문을 넣어 시간초과가 났다는 것이다. 여기서 for 문을 바깥으로 꺼내주고 시간초과는 해결, 두번째 실패는 for문을 N까지 돌려서 났다. N+1로 고쳐서 통과했다. 소스 코드 from _collections import deque for tc in range(1, 1 ..