SiO2whocodes

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net C++ 다익스트라 문제가 간결한 것에 비해 걸린 시간이 매우 김. 역시 골드는 만만하게 봐선 안돼 우선순위큐를 사용해서 다익스트라로 풀이하는 문제입니다. 접근방법 인접행렬을 사용했고, 우선순위큐를 사용했습니다. 방문 여부는 큐에서 뽑은 거리가 이미 그 노드까지의 최단경로와 같다면 그 노드에 대해서는 처리하지 않고 넘어가는 식 오답노트 우선순위 큐 안써서 시간초과 났었음 근데 우선순위 ..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net C++ BFS 수빈이가 동생이 있는 좌표까지 가는데 걸리는 최단시간을 구하는 문제이다. 수빈이는 1초에 앞,뒤,2배만큼 이동할 수 있고 최소한 몇초만에 찾는지 구하는 문제 접근방법 인접한 노드를 현위치에서 -1, +1, *2 위치로 생각하고 distances배열에 최단거리를 저장하면서 BFS 최단거리 문제로 풀었다. 오답노트 큐에 push할때 배열의 최대 범위를 넘어나서 런타임에러가 ..

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net C++ BFS 즐거운 미로탐색 갈수있는 길이 2차원 배열로 주어지고 0,0에서 n-1,m-1까지의 최단'거리'를 구하는 문제 경로가 아니라 인덱스를 저장할 필요는 없다 (parent배열 안갖고 있어도 된다는 소리) 접근방법 여느 BFS와 같이 큐에 인접한 노드를 저장하고 (여기서는 인접한 노드가 길이 있으며(maze배열에서 1), 아직 방문하지 않음(distances가 -1)) 동시에 인접한 노드들의 distances를 갱신하고 또 큐에서 인..