CEO

문제 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. �� www.acmicpc.net 문제 풀이 트리가 주어질 때, 가장 넓이가 높은 경우에 레벨과 넓이를 찾는 문제이다. 입력 예제의 그림을 보면 1을 기준으로 left child부터 인덱스가 할당되고, 1의 인덱스를 할당한 후에 right child의 인덱스를 할당하는 것을 알 수 있다. 이는 중위 순회를 통해 트리의 인덱스 번호를 부여한 것이라는 걸 알 수 있다. 중위 순회의 경우 트리 순회 문제에서 다루었다. 문제를 풀기 위해 다음과 같은 과정을 진행하면 답을 구..

문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 풀이 주어진 미로에는 2가지의 경우의 수가 존재한다. 첫 번째는 벽이 있는 경우이고, 두 번째는 벽이 없는 경우이다. 문제를 풀기 위해서는 벽을 최소한으로 부수고, [N, M]에 도착하는 경우를 반환하여야 한다. 만약 2개의 가중치가 아닌 여러 가중치가 설정되어 있다면, 다익스트라로 풀어야 한다. 하지만 문제에서는 벽이 없는 경우에 대한 우선순위를 주면 되므로 이전에 푼 숨바꼭질 3과 같이 BFS를 통해서도 풀 수 있다. 아래의 ..

문제 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 2부터 n -1 까지의 노드에 대한 부모를 찾는 문제이다. 이는 다른 그래프 문제에서 방문 여부를 탐색하는 것을 활용하면 쉽게 풀 수 있다. BFS를 통해 특정 노드를 방문할 때, 방문되지 않았다면 해당 노드의 부모는 현재 노드가 부모가 된다. 만약 예제 입력 1과 같을 경우, BFS로 통해 탐색하게 되면 1번 노드의 자식 노드들은 각각 4, 6이고 최초 방문 상태이므로 부모 노드가 1 임을 체크할 수 있다. 이처럼 모든 노드에 대해 방문하지 않은 경우 현재의 부모를 체크해두면 트리의 부모를 찾을 수 있다. 코..

문제 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 문제 풀이 트리를 순회하는 것은 깊이 우선으로 탐색하므로 재귀 호출을 사용하면 쉽게 구현할 수 있다. 재귀 호출을 언제 할지 구현하면 전위, 중위, 후위 순회를 할 수 있다. 즉, 재귀 호출을 할 때 부모를 언제 출력하느냐에 따라 순회 방법이 달라진다. 순회하는 방법은 아래와 같다. 전위 순회 : 부모 → 왼쪽 자식 → 오른쪽 자식 중위 순회 : 왼쪽 자식 → 부모 → 오른쪽 자식 후위 순회 : 왼쪽 자식 → 오른쪽 자식 → 부모 코드 from sys..

문제 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만�� www.acmicpc.net 문제 풀이 이모티콘을 출력하는데 걸리는 최소 시간은 이전에 다룬 1697 숨바꼭질 문제와 같이 트리의 가지를 뻣어나가며 정답을 찾을 수 있다. 이 문제도 마찬가지로 복사, 붙여넣기, 삭제와 같이 3가지의 경우로 가지를 뻣어나가면 된다. 가지를 뻣어나갈 때 현재 다음과 같은 처리가 필요하다. 현재 모니터에 표시된 이모티콘이 S보다 많을 경우 큐에 삽입할 필요가 없다. 모니터에 표시된 이모티콘이 0보다 작은 경우도 마찬가지이다. 가지를 뻣어나가며 현재 표시된 ..

숨바꼭질 시리즈 숨바꼭질 숨바꼭질 2 숨바꼭질 3 숨바꼭질 4 문제 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 문제 풀이 1697 숨바꼭질 문제에서 찾을 수 있는 경로를 출력하는 문제이다. 몇 초 만에 찾을 수 있는지 기록하는 것처럼 2차원 배열을 통해, 방문 경로를 기록해두면 쉽게 해결 할 수 있다. 예시에서는 그림과 같이 하나의 문제에 대해 2가지 경로를 출력하였지만 하나의 경로만 정상적으로 출력하여도 답으로 처리 되는 것 같다. 코드 from sys import..

숨바꼭질 시리즈 숨바꼭질 숨바꼭질 2 숨바꼭질 3 숨바꼭질 4 문제 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 문제 풀이 기본적인 풀이 방식은 1697 숨바꼭질과 같다. 하지만 순간이동 할 경우, 0초의 시간이 걸리므로 순간이동 하는 경우에 우선순위를 두어 처리하여야 한다. 즉, 가중치를 가지는 그래프가 된다는 것과 같다. 만약 현재 위치 - 1, 현재 위치 + 1, 현재 위치 * 2의 우선 순위가 각각 다르다면 다익스트라로 풀어야 한다. 하지만 문제에서는 현재 위치..

숨바꼭질 시리즈 숨바꼭질 숨바꼭질 2 숨바꼭질 3 숨바꼭질 4 문제 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 � www.acmicpc.net 문제 풀이 앞서 다룬 1697 숨바꼭질 문제에서 조건이 추가된 문제이다. 수빈이의 위치가 5, 동생의 위치가 17일 때 BFS를 통해 탐색해보면 위의 그림과 같이 가장 빠른 시간인 4초에 찾을 수 있는 방법은 2가지 라는 것을 알 수 있다. 즉, 이전 문제는 단순히 몇 초만에 찾을 수 있는가?를 묻는 문제였으면 가장 빠른 시간에 찾는 방법은 몇 가지인지를 ..