나그네

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를 진행한 횟수가 정..