개발윗미

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 from collections import deque def dfs(start) : visited[start] = 1 # 방문 처리 print(start, end=' ') for i in range(1, n + 1) : if visited[i] == 0 and graph[start][i] ==..

Python으로 구현한 17471번 게리맨더링 문제 풀이입니다. https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net from collections import defaultdict, deque def combinations(arr, r) : for i in range(len(arr)) : if r == 1 : yield [arr[i]] else : for next in combinations(arr[i+1:], r-1) : yield [arr[i]] + next def..

Python으로 구현한 16236번 아기 상어 문제 풀이입니다. https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net from collections import deque INF = 1e9 # 무한을 의미하는 값으로 10억을 설정 # 맵의 크기 N을 입력받기 n = int(input()) # 전체 모든 칸에 대한 정보 입력 array = [] for i in range(n) : array.append(list(map(int, input().s..

Python으로 구현한 3665번 최종 순위 문제 풀이입니다. https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net from collections import deque # 테스트 케이스만큼 반복 for tc in range(int(input())) : # 노드의 개수 입력 받기 n = int(input()) # 모든 노드에 대한 진입차수는 -으로 초기화 indegree = [0] * (n + 1) # 각 노드의 연결된 간선 정보를 담기위한 ..

Python으로 구현한 2887번 행성 터널 문제 풀이입니다. https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x) : # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x : parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 ..

Python으로 구현한 11404번 플로이드 문제 풀이입니다. https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수 및 간선의 개수를 입력받기 n = int(input()) m = int(input()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기 ..