https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net 문제 요약 NxN 체스판의 특정 위치에 하나의 나이트 M개의 상대편 말들의 위치 값이 주어졌을 때, 각 상대편 말을 잡기 위한 나이트의 최소 이동 수 계산하는 프로그램 [이동 방법] 현재 나이트 위치 (X, Y) (X-2, Y-1), (X-2, Y+1), (X-1, Y-2), (X-1, Y+2), (X+1, Y-2), (X+1, Y+2), (X+2, Y-1),..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 요약 수빈이가 이동할 수 있는 경로 X-1, X+1, X*2 동생을 찾을 수 있는 가장 빠른 시간은 몇 초인가? 범위 수빈이의 위치 N(0 ≤ N ≤ 100,000) 동생의 위치 K(0 ≤ K ≤ 100,000) 수빈이가 이동할 수 있는 경로는 3가지이다. - x-1 - x+1 - x*2 동생을 찾을 수 있는 가장 빠른 시간을 찾아야 한다. 위의 3가지 경로는 한 ..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 요약 N x M크기의 미로 1 : 이동할 수 있는 칸 0 : 이동할 수 없는 칸 (1, 1)에서 출발해 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하라 서로 인접한 칸으로만 이동 가능 (칸을 셀 때, 시작 위치와 도착 위치도 포함) 범위 N, M(2 ≤ N, M ≤ 100) 각각의 수들은 붙어서 입력으로 주어진다. 이동 가능한 방향은 인접칸으로만 가능하므로 상하좌우 dis 배열을 통해 이동횟수를 더하고 ..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제 요약 나이트가 이동하려고 하는 칸이 주어지고, 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 범위 체스판의 한 변의 길이 l(4 ≤ l ≤ 300) 체스판의 크기는 l × l 이 문제는 최단 이동 경로를 구하는 문제와 비슷하다. 최단 이동 경로 == 최소 이동 횟수와 동일하다 (거리가 1이므로, +1) 최단 이동 경로를 구하려면 BFS 알고리즘을 사용하면 된다. 이동할 수 있는 위치는..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 요약 이진트리를 입력받아 전위 순회, 중위 순회, 후위 순회 결과 출력하는 프로그램 범위 이진트리의 노드의 개수 N(1 ≤ N ≤ 26) 전위 순회, 중위 순회, 후위 순회 각 함수를 따로 만들어서 순서대로 출력해줬다. 각 순회는 문제에도 나와있듯이 - 전위 순회: 루트 - 왼쪽 - 오른쪽 - 중위 순회: 왼쪽 - 루트 - 오른쪽 - 후위 순회: 왼쪽 - 오른쪽 - 루트 순이므로 ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 요약 바이러스는 상하좌우 인접 빈칸으로 이동 가능 새로 세울 수 있는 벽의 개수 3개, 꼭 3개를 세워야 한다. 0 = 빈칸, 1 = 벽, 2 = 바이러스. 바이러스가 퍼질 수 없는 곳 = 안전 영역 안전 영역 크기의 최댓값을 구하라. 범위 세로 크기 N, 가로 크기 M (3 ≤ N, M ≤ 8) 사실 여기서 완전 탐색을 사용해도 되는지 몰랐다. 완전 탐색으로 3개의 벽을 세우고 바이러스를 퍼트리고 안..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 문제 요약 "처음에는" A, B 물통 == empty, C 물통 == full 물을 이리저리 붓고 A 물통이 비었을 때, C 물통에 담겨있을 수 있는 물의 양을 순서대로 출력해라. 물 붓는 방법 붓는 물통 빌 때까지 채워지는 물통 가득 찰 때까지 범위 부피 A, B, C (1≤A, B, C≤200) BFS로 풀 수 있는데, 물통 안에 들어있는 물의 양을 (a, b, c)라고 할..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 요약 나 - 아버지, 아버지 - 할아버지 : 1촌 나 - 할아버지 : 2촌 나 - 아버지 형제 : 3촌 주어진 두 사람의 촌수를 계산하라. (두 사람의 친척 관계가 전혀 없으면 -1 출력) 범위 전체 사람 수 n (1 ≤ n ≤ 100) 부모 자식들 간의 관계의 개수 m 처음에는 각 루트에서 구해야 하는 사람 노드로 이동하는 것을 생각했다. 하지만 그렇게 하는 것보다는 어..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 루트 없는 트리. 트리의 루트가 1일 때, 각 노드의 부모를 구하라 범위 노드의 개수 N (2 ≤ N ≤ 100,000) 모든 정점을 탐색해서 모든 노드의 부모 노드를 찾으면 되므로 이는 DFS 혹은 BFS 중 하나를 선택해서 코드를 구현하면 된다. BFS BFS는 한 노드에서부터 시작해서 방문한 노드를 큐에 넣으면서 진행한다. 큐에 들어간 노드의 인접 노드를 반복문을 통해 방문하게 되는데, 이때 x는 현재 방문 노드, y는 인접 노드를 의미하므로 ..