나그네

17071번: 숨바꼭질 5 문제 https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 수빈이(편의상 누나)는 다른 숨바꼭질 문제들처럼 +1, -1, ×2로 이동 가능하고 시간은 1초 걸린다. 대신 동생이 1초에 1칸, 2초에 2칸,... N초에 N칸씩 움직인다. 따라서 BFS 알고리즘을 사용해서 풀 수 있다. 처음 접근 방식은 각각에 대해 BFS를 하며 (동생은 사실 하나만 이동하지만) 시간 단위로 이동하고..

4179번: 불! 문제 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 풀이 재민이가 불을 피해 가장자리로 가서 탈출할 수 있으면 탈출하는 최단 시간을, 탈출할 수 없으면 IMPOSSIBLE을 출력하는 문제다. 틀린 풀이 BFS를 시작할 때 재민이는 1부터 시작하고 불은 1001부터 시작하도록 해서 재민이 먼저 이동, 그다음 불이 이동하도록 했다. 이동할 때마다 visited 배열 값이 1씩 증가하도록 해서 시간을 계산했다. 큐..

5719번: 거의 최단 경로 문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 정점의 수와 단방향 간선들이 주어지고 시작점, 도착점이 주어질 때 최단 경로가 아닌 경로들 중 가장 짧은 경로의 길이를 구하는 문제다. 다익스트라 알고리즘을 주로 사용한다. [다익스트라 알고리즘 알아보기] 먼저 다익스트라 알고리즘으로 최단 경로를 구해준다. 이 경우 시작점부터 각 정점까지의 최단경로가 모두 구할 수 있다. 이제 ..

2458번: 키 순서 문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이 학생들 간 키를 비교해 자신이 몇 번째인지 알 수 있는 학생의 수를 구하는 문제다. 플로이드-워셜 알고리즘을 사용해 주어진 간선은 1, 나머지는 INF로 두고 플로이드-워셜을 돌린다. 정점 u, v의 키를 비교할 때 dist[u][v]가 INF가 아니라면 u보다 v가 키가 큰 것이고 dist[v][u]가 INF가 아니라면 v보다 u가 키가 큰 것이다. 둘 다 아니라면..

1389번: 케빈 베이컨의 6단계 법칙 문제 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 플로이드-워셜 알고리즘을 사용해 각 사람이 다른 사람에 이르기까지의 단계를 각각 구해 케빈 베이컨의 수를 구하고, 최솟값을 가지는 사람의 번호를 출력하는 문제다. 코드 #include using namespace std; #define INF 1e9 int main() { ios::sync_with_..

11403번: 경로 찾기 문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 (i, j)의 값이 0이면 연결되어 있지 않은 것이고 1이면 i->j 연결되어 있는 것이다. 따라서 dist[i][j]에 입력을 받아 0이면 연결되어 있지 않으므로 INF로, 1이면 1을 저장해 준다. 플로이드-워셜 알고리즘으로 모든 최단거리를 구하고 i->j로 갈 수 있는 경우엔 1을, INF라면 0을 출력해 주면 된다. 코드 #include using namespace std; #define INF ..

9019번: DSLR 문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 D, S, L, R 쿼리를 사용해 A에서 B로 가는 최소 쿼리를 구하는 문제다. BFS로 문제를 해결할 수 있으며 시간초과에 유의해야 한다. visited 배열은 몇 번째 방문인지 나타내는 정수와 해당 정수까지 도달하는 최단 쿼리를 담고 있다. 처음에 L, R 쿼리 때문에 A, B를 string으로 수를 입력받아 또 정수로 바꾸고.. 이런 과정을 거쳤으..

2206번: 벽 부수고 이동하기 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 (1,1)부터 (N, M)까지 최단 경로를 구하는 문제다. 단, 벽이 있는 곳은 지나갈 수 없으며 단 한 번만 벽을 부술 수 있다. 틀린 풀이 벽이 있는 모든 점에 대해 그 벽이 없을 때의 경로를 탐색하는 방법으로 코드를 작성했고 시간초과가 났다. 벽의 개수만큼 BFS를 해야 하기 때문이다. 맞은 풀이 시간초과가 나지 않기 위해 ..

13913번: 숨바꼭질 4 문제 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 1697번 숨바꼭질 문제의 확장된 버전이다. 최단 시간뿐 아니라 그 경로도 구하는 문제다. [1697 숨바꼭질 문제] | [1697 숨바꼭질 풀이] x+1, x-1, x*2를 탐색할 때 한 번 방문한 점은 다시 방문하지 않으므로 어느 점에 방문할 때 어느 점에서 이동했는지를 기록하는 bef 배열을 만들었다. 존재할 수 없는 -..

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으로 바..