https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 시간 복잡도는 어 음... 잘 모르겠다. 아는 건 우선 deque 라이브러리는 탐색을 수행할때 O(N)을 잡아먹는 빠른 라이브러리하는건 안다. from collections import deque n,k = map(int,input().split()) visited = [False] * 100001 dx = [-1, 1 , 2] def bfs(n,k): end = k q..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net from collections import deque n, m = map(int, input().split()) graph = [0 for _ in range(101)] visited = [False] * 101 ladder = {} snake = {} for _ in range(n): x, y = map(int,input().split()) ladd..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 잘못된 풀이 - 시간초과로 인해 문제가 발생한다. 당연히 부르드포스로 접근을 하게 되면서 문제가 풀리기는 하지만 시간 초과의 문제를 만나게 되었다. import sys from collections import deque import copy n, m = map(int, sys.stdin.readline().split()) graph = [] for i in range(n..

https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net import sys from collections import deque sys.setrecursionlimit(100000) n, m, r = map(int, sys.stdin.readline().split()) graph = [[] for i in range(n + 1)] visited = [False] * (n + 1)..

https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 이 문제의 시간 복잡도는 n^2? for 문이랑 while문이 들어가니 그렇게 생각한다 import sys from collections import deque sys.setrecursionlimit(100000) n, m, r = map(int, sys.stdin.readline().split()) graph = [[] ..

https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 시간 복잡도는 N^2 이라 생각한다. 아닌가? N 인가? import sys sys.setrecursionlimit(100000) n, m, r = map(int, sys.stdin.readline().split()) graph = [[] for i in range(n + 1)] visited = [False] * (n + ..

문제 https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 시간 복잡도 시간 복잡도는 재귀를 써서? 잘 모르겠지만 n^2 일거 같다. 코드 import sys sys.setrecursionlimit(100000) n, m, r = map(int, sys.stdin.readline().split()) graph = [[] for i in range(n + 1)] visited =..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net import sys from collections import deque m, n, k = map(int,sys.stdin.readline().split()) graph = [[0]*n for i in range(m)] for _ in range(k): x1,y1,x2,y2 = map(int,sys.stdin.readline().split()) for i in range(y1,..