개미의 개열시미 프로그래밍

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net [실패한 유니온 파인드 풀이 코드] # 유니온 파인드로 풀어봄 parent = [i for i in range(n+1)] cnt_list = [0 for _ in range(n+1)] def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] de..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이 코드] import sys n = int(input()) graph = [[] for _ in range(n + 1)] parent = [[] for _ in range(n + 1)] # 트리를 그래프 형태로 생성 for _ in range(n - 1): i, j = map(int, sys.stdin.readline().split()) graph[i].append(j) graph[j].append(i) def dfs(start): stack = [sta..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net [풀이 코드] from sys import stdin from collections import deque input = stdin.readline dx = [-1, 1, 0, 0, -1, -1, 1, 1] dy = [0, 0, -1, 1, -1, 1, -1, 1] def bfs(i, j): queue = deque() queue.append((i, j)) while queue: x, y =..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net [풀이 코드] import sys from sys import stdin sys.setrecursionlimit(10000) input = stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n + 1)] visited = [False] * (n+1) c..

드디어 BFS와 DFS 단계별 풀어보기 마지막 문제인 이분그래프 입니다. 마지막 문제를 가볍게 풀고 싶었지만 문제를 이해하는 것부터 막혔습니다.. 풀이도 어떻게 풀어야할지 몰라 결국 답을 찾아봤습니다. https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 풀이코드 from collections import deque from sys import stdin def bfs(start): visit[start] = 1 # 시작점은 1로 시작 ..

단계별 풀기 dfs, bfs의 8문제입니다.. 한문제만 더 풀면 다른 파트를 공부할 수 있습니다ㅜ https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이코드 from collections import deque from sys import stdin def bfs(x, y): # 나이트의 이동범위 dx = [-1, 1, -2, 2, -2, 2, -1, 1] dy = [-2, -2, -1, -1, 1, 1, 2, 2] queue = deque() q..

이번 문제는 단계별 풀기 bfs, dfs파트에 7번째 문제인 벽 부수고 이동하기 문제입니다. https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 코드 # 벽을 하나 부쉴 수 있다는 점 # 불가능이면 -1 # 최단거리 = bfs from collections import deque from sys import stdin n, m = map(int, stdin.readline().split()) graph = [] for..

오늘은 단계별로 풀어보기 'bfs와 dfs' 파트 중 7번째 문제입니다. 앞으로 세문제 정도 남았는데 시험기간이 끝나면 하루 두 세 문제씩 해서 모든 파트를 빨리 끝내고 싶습니다. https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이코드 # 예시 5 - 10 - 9 - 18 - 17 # 가장 빠른 시간을 출력하기 => 가장 빠른 거리를 찾는 문제와 유사하다고 생각 => bfs문제 from collections impo..