본문 바로가기

Algorithm Problems/그래프

 (50)
[Python/백준] 1991번: 트리 순회 문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 요약 이진 트리를 입력 받고, 전위 순회, 중위 순회, 후위 순회한 결과를 출력한다. + 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. + 자식 노드가 없는 경우에는 .으로 표현한다. 코드 import sys input = sys.stdin.readline def preorder(root): # 전위 순회 if root != '.': ..
[백준/Python] 2667번: 단지번호붙이기 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 요약 N × N 크기의 지도에서 총 단지 수와 단지 별 집의 수를 출력한다. 단지는 연결된 집의 모임이다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 위아래로 다른 집이 있는 경우이다. + 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. + 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력한다. 코드 def dfs(x, y): global cnt check[x][y] =..
[백준/Python] 2468번: 안전 영역 문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 요약 지역의 높이 정보를 가진 크기가 N × N 배열을 입력 받는다. 비의 양에 때라 일정 높이 이하의 모든 지점은 물에 잠긴다. 첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다. + 안전한 영역은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽, 왼쪽으로 인접해 있으며 그 크기가 최대인 영역이다. 코드 from collections import deque def bfs..
[백준/Python] 1260번: DFS와 BFS 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 요약 N개의 정점과 정점을 잇는 M개의 간선으로 이루어진 그래프를 입력 받고, 그래프를 V번 정점부터 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력한다. + 정점 번호는 1번부터 N까지 존재한다. + 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다. 코드 from collections import deque de..
[백준/python] 13023번: ABCDE 문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 요약 N명의 캠프 인원 중 M가지 친구 관계를 입력 받는다. 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하면 1, 없으면 0을 출력한다. - A는 B와 친구다. - B는 C와 친구다. - C는 D와 친구다. - D는 E와 친구다. 코드 def dfs(num, depth): if depth == 5: print(1) exit() for n_num in graph[num]: if check[n_num] == 0: # 아직 탐색하지 않은 친구라면 check[n_num] = ..
[백준/python] 2644번: 촌수계산 문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 요약 n명의 부모 자식들 간 관계를 m개 입력 받고, 서로 다른 두 사람의 촌수를 출력한다. + 기본적으로 부모와 자식 사이를 1촌으로 정의한다. + 사람들은 1, 2, 3, ... 의 연속된 번호로 각각 표시된다. + 각 사람의 부모는 최대 한 명만 주어진다. 코드 from collections import deque def bfs(): queue = deque([..

티스토리툴바