나그네

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

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..

1963번: 소수 경로 문제 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 4자리 소수 A, B를 입력받고 A를 적절히 바꾸어 B를 만드는데 몇 번 만에 바꿀 수 있는지 구하는 문제다. 바꾸는 데는 규칙이 있다. 1. 한 번에 한 자리 수만 바꿀 수 있다. 2. 바뀐 수도 반드시 소수여야 한다. 소수인지 판단하기 위해 에라토스테네스의 체를 사용해 소수를 걸러준다. 그리고 bfs를 돌렸다. A를 방문처리하고 큐에 넣는다. 이때 큐는 pair를 원소..

1260번: DFS와 BFS 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 dfs와 bfs의 기본 사용 방법을 연습할 수 있는 문제다. 간선이 양방향이므로 x, y를 입력받아 graph[x][y] = 1, graph[y][x] = 1로 해준다. 시작 정점부터 dfs를 돌리면 방문처리를 한 후 정점에서 연결된 위치가 아직 방문하지 않았다면 해당 정점으로 dfs를 다시 진행한다. 이를 반복하여 계속..

1012번: 유기농 배추 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 잘 알려진 bfs 문제. M×N 배열을 모두 돌면서 값이 1인 동시에 아직 방문하지 않은 점들에 대해 bfs를 시행한다. bfs에선 해당 좌표를 방문처리한 후 상하좌우를 하나씩 체크하며 값이 1인 동시에 아직 방문하지 않았다면 큐에 추가해 준다. 위 방법을 큐가 빌 때까지 반복한다. bfs를 한 번 진행하면 인접해있는 모든 배추는 방문하게 되므로, bfs를 진행한 횟수가 정..