📍문제 링크 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 📍알고리즘 분류 - 그래프 이론 - 그래프 탐색 - 트리 - 너비 우선 탐색 - 깊이 우선 탐색 📍문제 풀이 - 간선에 가중치를 갖는 트리가 주어질 때, 테스트 케이스에서 주어지는 시작점부터 끝점까지의 거리를 구하라 - DFS를 활용한다- 거리를 계산하는 로직은 아래와 같다1️⃣정점의 갯수 + 1 만큼의 길이를 갖는 빈 배열 distance를 만든다 (계산의 편의상)2️⃣현재 정점의 이웃 정점들을 순회하며 distance[이웃 정..

📍문제 링크 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 📍알고리즘 분류 - 그래프 이론 - 그래프 탐색 - 너비 우선 탐색 - 깊이 우선 탐색 📍문제 풀이 높이 m, 너비 n 의 사각형이 주어질 때, 1번째 row의 0이 마지막 row의 0까지 연결되어 있는지를 확인 DFS를 통해 연결된 경로가 있으면 바로 YES를 출력하면 된다 📍코드 (JavaScript) const [in1, ...map] = re..

📍문제 링크 https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 📍알고리즘 분류 - 구현 - 그래프 이론 - 브루트포스 - 그래프 탐색 - 너비 우선 탐색 - 깊이 우선 탐색 📍문제 풀이 구현으로도 해결할 수 있는 문제이지만 DFS를 사용해서 풀자 - 크기가 작아서 구현으로 해결 가능 DFS를 사용하는 이유 - 빠르게 목표 지점에 도달하는 경로 하나만 찾으면 프로그램을 종료할 수 있어서 📍의사 코드 /* 1. 행렬 형태로 주어진 데이터를 2차원 배열로..

📍문제 링크 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 - 그래프 이론 - 그래프 탐색 - 트리 - 깊이 우선 탐색 - 트리에서의 다이나믹 프로그래밍 📍문제 풀이 트리와 이차원 배열이 주어진다. 이차원 배열은 [정점 번호, 숫자] 형태의 원소를 갖고 있다. 이차원 배열을 순회하며, 정점 번호에 해당하는 정점의 모든 자식 노드에 숫자를 더해주면 된다. - DFS를 사용하는 이유 사실 어차피 모든 그래..