와드의 블로그

문제트리가 주어지고, 그중 하나의 노드를 지웠을 때 남은 트리에서 리프 노드(단말 노드)의 개수를 구하는 문제입니다. 노드를 지우면 그 노드와 해당 노드를 루트로 하는 모든 하위 서브 트리도 함께 지워집니다.입력:첫째 줄에 트리의 노드 개수 N (1 ≤ N ≤ 50)이 주어집니다.둘째 줄에 0번 노드부터 N-1번 노드까지 각 노드의 부모가 주어집니다. (부모가 없으면 -1)셋째 줄에 지울 노드의 번호가 주어집니다.출력: 주어진 노드를 지운 후 남은 트리에서 리프 노드의 개수를 출력합니다.링크: https://www.acmicpc.net/problem/1068풀이 1: BFS 탐색과 예외 처리이 문제는 그래프(트리) 탐색 중에 지워질 노드를 만나면 탐색을 건너뛰는 방식으로 해결할 수 있습니다. 큐(Queu..

문제사각형 모양의 판 위에 치즈가 놓여 있습니다. 이 치즈는 공기와 접촉하면 한 시간 뒤에 녹아 없어집니다. 단, 치즈 내부에 있는 빈 공간(구멍)은 외부 공기와 닿지 않는 것으로 취급되어, 구멍과만 닿아있는 치즈는 녹지 않습니다. 모든 치즈가 녹아 없어지는 데 걸리는 시간과, 치즈가 모두 녹기 한 시간 전에 남아있던 치즈 조각의 개수를 구하는 문제입니다.입력: 첫째 줄에 판의 세로와 가로 길이가 주어지고, 둘째 줄부터 판의 모양(1은 치즈, 0은 빈 칸)이 주어집니다.출력: 첫째 줄에 치즈가 모두 녹아서 없어지는 데 걸리는 시간, 둘째 줄에 모두 녹기 한 시간 전에 남아있는 치즈 조각의 개수를 출력합니다.링크: https://www.acmicpc.net/problem/2636풀이: 외부 공기 기준 BF..

문제크기가 N인 수열 A가 주어집니다. 수열의 각 원소 A_i에 대해서 오큰수 NGE(i)를 구하려고 합니다. A_i의 오큰수는 오른쪽에 있으면서 A_i보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미합니다. 그러한 수가 없는 경우에 오큰수는 -1입니다.입력: 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어집니다. 둘째 줄에 수열 A의 원소들이 주어집니다.출력: 총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력합니다.링크: https://www.acmicpc.net/problem/17298풀이: 스택을 활용한 O(N) 탐색수열의 크기가 최대 1,000,000이므로 이중 반복문으로 모든 원소의 오른쪽을 확인하면 O(N^2)으로 시간 초과가 발생합..

문제연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있습니다. 연구소는 빈 칸(0), 벽(1), 바이러스(2)로 이루어져 있습니다. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있습니다. 새로 세울 수 있는 벽의 개수는 무조건 3개이며, 꼭 3개를 세워야 합니다. 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 합니다. 안전 영역 크기의 최댓값을 구하는 문제입니다.입력: 첫째 줄에 세로 크기 N과 가로 크기 M이 주어집니다. (3 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에 연구소의 지도가 주어집니다.출력: 얻을 수 있는 안전 영역의 최대 크기를 출력합니다.링크: https://www.acmicpc.net/probl..

문제어떤 해커가 회사의 컴퓨터를 해킹하려고 합니다. 이 회사의 컴퓨터는 신뢰하는 관계와 신뢰하지 않는 관계로 이루어져 있습니다. A가 B를 신뢰하는 경우에는 B를 해킹하면 A도 해킹할 수 있습니다. 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력하는 문제입니다.입력: 첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 10,000)과 신뢰하는 관계의 수 M (1 ≤ M ≤ 100,000)이 주어집니다. 둘째 줄부터 M개의 줄에 신뢰하는 관계 A, B가 주어집니다.출력: 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 공백으로 구분하여 출력합니다.링크: https://www.acmicpc.net/problem/1325풀이: 방향 그래프 설계와 DFS 탐색한 컴퓨터를 해..