나그네

13549번: 숨바꼭질 3 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 다른 숨바꼭질 문제처럼 너비 우선 탐색(BFS)으로 해결할 수 있다. 단, x*2는 0초이므로 가장 우선적으로 해줘야 한다. 그리고 x+1과 x-1도 같은 1초가 걸리지만 뒤로 갔다가 ×2 하는 게 더 시간이 적게 걸릴 것이므로 x-1가 x+1보다 우선순위가 높다. visited 배열을 -1로 초기화해주고 시작지점을 0으로 바..

12851번: 숨바꼭질 2 문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 BFS로 풀었다. 큐에는 pair로 좌표와 걸린 시간을 넣어줬다. 처음으로 K위치에 도달한 경우, m을 걸린 시간으로 할당하고 cnt++ 해준다. BFS 특성상 이후 다시 K에 도달하는 경우는 반드시 걸린 시간이 같거나 길 수밖에 없다. 따라서 K에 도달할 때마다 cnt++ 해주고 처음으로 더 긴 시간이 되면 BFS를 탈출..

1697번: 숨바꼭질 문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS로 현재 위치로부터 +1, -1, ×2인 위치를 탐색한다. 만약 범위를 만족하면서 아직 방문하지 않았다면 큐에 추가해 주며 반복한다. visited 배열을 +1씩 해가며 몇 번만에 도달하는지 확인을 했다. visited[k] 값을 출력하면 된다. 코드 #include using namespace std; int n, k; vector..

1865번: 웜홀 문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 어느 시작점에서 다시 시작 지점으로 돌아올 때 시간이 되돌아갈 수 있는지 여부를 구하는 문제다. 벨만 포드 알고리즘을 사용해 풀 수 있다. 도로는 양방향이지만 웜홀은 단방향임을 주의해야 한다. 처음엔 dist[1] < 0 이면 YES를 출력하도록 했다. 그러나 2%틀을 받고 모든 정점에서 다 해보는 코드를 짰는데 90% 언저리에서 시간초과가 났다. 결국 벨..

11657번: 타임머신 문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 그래프에서 1번 정점으로부터 각 정점으로의 최단 거리를 구하는 문제다. 가중치가 음수도 가능하므로 기본적인 벨만-포드 알고리즘으로 풀 수 있는 문제. 만약 무한정 작아질 수 있는 루프가 있으면 -1을 출력하면 된다. 코드 #include using namespace std; #define INF 1e18..

1016번: 제곱 ㄴㄴ 수 문제 https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 풀이 min 이상 max 이하의 제곱 ㄴㄴ 수의 개수를 구하는 문제다. 제곱 ㄴㄴ 수란 어느 제곱수로 나누어 떨어지지 않는 수를 말한다. 이 문제의 핵심은 에라토스테네스의 체의 변형이다. 1 ≤ min ≤ 1,000,000,000,000 min ≤ max ≤ min + 1,000,000 위와 같은 범위 때문에 애를 먹었다. 아래 범위 조건 때문에 0..

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 문제 https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 b로 이동했다면 bef[b] = a 형태로 저장하고 다익스트라 알고리즘이 끝난 후 bef[M-1]부터 역으로 돌아가며 경로를 찾아낸다. 비슷한 문제로 [11779 최소비용 구하기 2 문제] | [11779 최소비용 구하기 2 해설]가 있다. 코드 #include using namespace std; #define INF 1000000000 int T, N, M; vector graph[20]; // [정점][다음 정점, 거리] vector dist(20, INF), visited(20, 0)..

2307번: 도로검문 문제 https://www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리 www.acmicpc.net 풀이 어느 한 간선을 차단하여 1에서 N까지 최단 경로가 얼마나 거리를 늘릴 수 있는지 구하는 문제다. 다익스트라 알고리즘으로 해결할 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 이 문제에서 중요한 것은 최단 경로 이외엔 차단할 필요가 없다. 왜냐하면 어차피 최단 경로로 지나가면 그만이기 때문이다. 그럼 먼저 ..

1545번: 안티 팰린드롬 문제 https://www.acmicpc.net/problem/1545 1545번: 안티 팰린드롬 만약 어떤 문자열 P가 있을 때, P[i]와 P[n-i-1] (0 ≤ i

14284번: 간선 이어가기 2 문제 https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 풀이 여러 정점 중 두 정점이 연결될 때 간선의 가중치가 최소가 되는 값을 구하는 것이므로 기본적인 다익스트라 알고리즘을 사용해 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 코드 #include using namespace std; #define INF 2147483647 int mai..