전체 글65 [백준][파이썬]11403번: 경로 찾기 문제 출처 : www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 내 풀이 각 정점마다 dfs를 돌면서 연결된 정점을 check에 방문처리해 준 후에 출력하도록 코드를 짰다. import sys input = sys.stdin.readline def dfs(v): for i in range(n): if check[i] == 0 and arr[v][i] == 1: check[i] = 1 dfs(i) n = int(input()) arr = [] for i in range(n): arr.append(list.. 2021. 4. 12. [백준][파이썬]1260번: DFS와 BFS 문제 출처 : www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 내 풀이 bfs와 dfs를 간단히 구현해보는 문제였다. import sys from collections import deque input = sys.stdin.readline def dfs(v): check[v] = 1 print(v, end = ' ') for i in range(1, n + 1): if check[i] == 0 and arr[v][i] =.. 2021. 4. 12. 탐색 알고리즘 DFS/BFS 들어가기 전에 그래프를 통한 비교 그래프는 노드(node)와 간선(edge)으로 표현되며 이때 노드를 정점(vertex)이라고도 한다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현 할 수 있다. 1. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 2. 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 일반적으로는 인접 리스트의 방식이 더 효율적이다. 인접 행렬의 경우, 정점의 개수 N만큼 도는 2중 for문을 돌려 두 정점 간에 간선이 존재하는지를 확인해야하기 때문이다. 인접 행렬의 시간 복잡도 : O(N²) DFS(깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색한다. 이름에서 알 수 있듯이 단순하게 가장 깊숙이 위치하는 노드에 닿을 때까지 확인(탐색)하면 된다.. 2021. 4. 12. [백준][파이썬]2775번: 부녀회장이 될테야 문제 출처 : www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 내 풀이 직접 그려보며 확인해본 결과 k층 n호에 사는 사람의 수는 (k층 n - 1 호에 사는 사람의 수) + (k - 1층 n호에 사는 사람의 수) 라는 규칙이 나왔다. import sys input = sys.stdin.readline t = int(input()) for i in range(t): k = int(input()) n = int(input()) arr = [[i for i in range(n + 1)] for _ in.. 2021. 4. 11. 이전 1 ··· 3 4 5 6 7 8 9 ··· 17 다음
