이마닷의 블로그

0. 문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 문제분석 - 트리라는 자료구조의 특성을 잘 알고 있다면 어렵지 않게 풀 수 있는 문제로, 트리가 가지고 있는 특성을 통해 리프노드를 찾기 위해서는 dfs를 사용해 문제를 풀어야 함을 알 수 있다. 트리는 cycle이 존재하지 않는 그래프이다. 하나의 트리는 하나의 루트만 존재한다. 루트가 여러 개라면 그것은 트리가 여러 개인 forest. 트리는 방향성이 존재하는(부모-자식)..

0. 문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 1. 문제분석 - 한 칸(노드)에서 시작해서 상하좌우로 인접한 칸을 연속해서 탐색한다는 점에서 DFS 또는 BFS 알고리즘을 사용..